부분 결과원문 확인
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQPCody Murray, Ryan Williams · 2018STOC 2018 (Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing), 890–901쪽 · 학술지판 SIAM Journal on Computing 49(5) (2020) · ECCC TR17-188 (2017)비결정적 준다항 시간에 풀리는 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. williams-2014 의 NEXP 를 훨씬 작은 종류로 낮춰, NP 에 대한 하한 쪽으로 한 걸음 다가선 결과다. ACC⁰ 하한이 지금 어디까지 왔는지 확인하려는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:저자 공개본을 열어 초록과 서론을 읽음.원문 주소 (eccc.weizmann.ac.il)이 카드를 붙인 자료 6