라즈 보 로프는 이분 그래프에 대한 완벽한 매칭 함수를 계산하는 모든 모노톤 회로가 최소한
엔Ω(로그엔)게이트 (그는 “논리적 영구”라고 불렀습니다). 그 이후 같은 문제에 대한 더 나은 하한이 입증 되었습니까? (말하다
2엔ϵ?) 내가 기억하는 한이 문제는 1990 년대 중반에 열려있었습니다.
clique 함수에는 지수 크기의 모노톤 회로 등이 필요하다는 것을 알고 있지만 완벽하게 일치하는 데 관심이 있습니다.
답변
Eva Tardos는 폴리 크기 회로는 있지만 지수 크기 모노톤 회로가 필요한 모노톤 부울 함수가 있음을 보여줌으로써 격차가 실제로 지수임을 증명했습니다. 수퍼 다항식보다 더 좋은 것은 매칭으로 알려져 있지 않습니다.
Raz는 매칭을위한 모노톤 회로가 선형 깊이를 갖도록합니다. (오타를 지적 해 주셔서 감사합니다.)
AFAIK, 우리는 더 잘 알지 못합니다.
참조 : (1) http://www.springerlink.com/index/P25X5838624J0352.pdf
(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps