완벽한 매칭의 모노톤 회로 복잡성에서 하한 개선? 모든 모노톤 회로가

라즈 보 로프는 이분 그래프에 대한 완벽한 매칭 함수를 계산하는 모든 모노톤 회로가 최소한 $n^{Ω (\log n)}$

엔Ω(로그⁡엔)

게이트 (그는 “논리적 영구”라고 불렀습니다). 그 이후 같은 문제에 대한 더 나은 하한이 입증 되었습니까? (말하다 $2^{n^{ϵ}}$

2엔ϵ

?) 내가 기억하는 한이 문제는 1990 년대 중반에 열려있었습니다.

clique 함수에는 지수 크기의 모노톤 회로 등이 필요하다는 것을 알고 있지만 완벽하게 일치하는 데 관심이 있습니다.

Eva Tardos는 폴리 크기 회로는 있지만 지수 크기 모노톤 회로가 필요한 모노톤 부울 함수가 있음을 보여줌으로써 격차가 실제로 지수임을 증명했습니다. 수퍼 다항식보다 더 좋은 것은 매칭으로 알려져 있지 않습니다.

Raz는 매칭을위한 모노톤 회로가 선형 깊이를 갖도록합니다. (오타를 지적 해 주셔서 감사합니다.)

AFAIK, 우리는 더 잘 알지 못합니다.

How IT