역사원문 확인
A Short History of Computational ComplexityLance Fortnow, Steven Homer · 2003Bulletin of the EATCS 80 (2003년 6월) — Computational Complexity Column · 공개본 원고 날짜는 2002년 11월 14일1936년 Turing 의 기계에서 시작해 2000년대 초까지 계산 복잡도 이론이 걸어온 길을 십 년 단위로 짚은 역사 개관이다. 다항 시간과 NP-완전성의 등장, 1970년대의 복잡도 클래스들, 1980년대의 회로, 1990년대의 양자 계산과 증명 복잡도를 차례로 다룬다. 2-1 의 연표를 쓰거나 고치려는 사람이 사건의 순서와 맥락을 맞춰 볼 때 가장 먼저 펼 문헌이다.
확인:저자 공개본 PDF 를 열어 제목·저자·머리말을 읽었고, 실린 곳(권·연월)은 저자가 공개한 출판 목록(BibTeX)으로 확인했다.