접근서지만 확인
Circuit minimization problemValentine Kabanets, Jin-Yi Cai · 2000STOC 2000 (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing), 73–79쪽 · ECCC TR99-045 (1999)최소 회로 크기 문제(MCSP)가 왜 P 에 속한다고도 NP-완전이라고도 증명하기 어려운지를 밝힌 논문이다. 이 문제가 쉽다고 가정하면 놀라운 귀결들이 따라 나오고, NP-완전임을 증명하면 그것만으로 강한 회로 하한이 나온다는 것을 보인다. 메타 복잡도 접근의 출발점을 찾는 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:ECCC TR99-045 의 초록까지 확인. 본문을 읽었다는 기록은 없고, 귀결에 관한 서술은 Aaronson 2017 §6.2.5 의 각주와 Allender 2020 §4 로 확인.원문 주소 (eccc.weizmann.ac.il)이 카드를 붙인 자료 1