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

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

$2^{n^\epsilon}$?) 내가 기억하는 한이 문제는 1990 년대 중반에 열려있었습니다.

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

답변