접근원문 확인
The relative efficiency of propositional proof systemsStephen A. Cook, Robert A. Reckhow · 1979The Journal of Symbolic Logic 44(1), 36–50쪽 (1979) · 예비판 「On the lengths of proofs in the propositional calculus」, STOC 1974, 135–148쪽명제 증명 체계를 일반적으로 정의하고 증명 길이의 문제를 NP 대 coNP 문제와 이은 논문이다. 모든 항진식에 다항 길이의 증명을 주는 증명 체계가 있는 것과 NP = coNP 가 같은 말임을 보여 증명 복잡도라는 분야의 틀을 세웠다. 증명 복잡도 접근을 공부하려는 독자의 출발점이다. Cook 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 §1(명제 1.1·1.4, 정의 1.3·1.5)을 읽음.원문 주소 (www.cs.toronto.edu)이 카드를 붙인 자료 3