접근서지만 확인
Super-logarithmic depth lower bounds via the direct sum in communication complexityMauricio Karchmer, Ran Raz, Avi Wigderson · 1995Computational Complexity 5(3–4), 191–204쪽 (1995) · 학회 발표 Structure in Complexity Theory, Sixth Annual Conference (1991), 299–304쪽두 함수를 합성하면 필요한 회로 깊이가 거의 더해진다는 추측(KRW 추측)을 내놓은 논문으로 널리 인용된다. 추측이 참이면 다항 시간 문제 가운데 로그 깊이 회로로는 풀 수 없는 것이 있다(P ≠ NC¹)는 결론이 나온다고 알려져 있다. 통신 복잡도를 거쳐 깊이 하한을 얻으려는 연구 방향을 소개하는 글의 출전이다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 서지를 확인했다(본문은 열지 못함).