부분 결과서지만 확인
Monotone circuits for matching require linear depthRan Raz, Avi Wigderson · 1992Journal of the ACM 39(3), 736–744쪽 (1992) · 학회 발표 STOC 1990 (Proceedings of the 22nd Annual ACM Symposium on Theory of Computing), 287–292쪽완전 매칭 함수를 계산하는 단조 회로의 깊이가 Ω(n) 이어야 함을 보인 논문이다. 매칭은 다항 시간에 풀리는 문제인데도 단조 회로로는 깊이가 선형이어야 하므로, 단조 회로와 일반 회로의 깊이 사이에 지수적 격차가 있음이 따라 나온다. 단조 하한이 왜 일반 하한으로 옮겨지지 않는지 설명하는 글에 쓴다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.