장벽서지만 확인
Natural Proofs versus DerandomizationR. Ryan Williams · 2016SIAM Journal on Computing 45(2), 497–529쪽 (2016) · 학회 발표 STOC 2013 (Proceedings of the 45th Annual ACM Symposium on Theory of Computing), 21–30쪽 · arXiv:1212.1891NEXP 가 어떤 회로 클래스에 들지 않음을 보이는 일은 그 클래스에 유용한 「구성적」 성질을 내놓는 일과 같음을 보인 논문이다. 자연 증명의 세 조건 가운데 구성성은 NEXP 하한에서조차 피할 수 없다는 뜻이다. 또 자연 성질이 없음을 보이는 일이 본질적으로 탈무작위화 문제임을 밝힌다. 자연 증명 장벽을 어떻게 비켜 갈지 논하는 글이 2-2 의 원전(razborov-rudich-1997) 다음으로 인용할 문헌이다.
확인:학술지판과 학회판은 Crossref 등록 기록으로, 초록은 Crossref 와 arXiv 초록 페이지로 확인했다.