개관원문 확인
Average-Case ComplexityA. Bogdanov, L. Trevisan · 2006Foundations and Trends in Theoretical Computer Science 2(1), 1–106쪽 (2006) · arXiv:cs/0606037 (2021년 개정판)평균적 복잡도 이론을 정리한 100여 쪽의 개관이다. Levin 의 완전성 이론과, 최악의 경우를 평균적 경우로 옮기는 환원의 한계를 다룬다. 2-3 의 평균적 복잡도 글이 여러 고전 논문의 내용을 이 개관으로 확인했다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(2021년 개정판)의 초록과 §1.1·§1.2 를 읽음.