문헌 카드

P 대 NP 가 표준 공리계와 독립일 수 있는가를 논리학에 익숙하지 않은 독자를 위해 풀어 쓴 개관이다. ZF 집합론의 속성 강의에서 시작해 오라클 독립성, 자연 증명, Razborov·Raz·DeMillo–Lipton 등의 독립성 결과, 강한 이론과의 독립성을 증명하기 어려운 까닭을 다룬다. 「증명도 반증도 안 되는 문제일 수 있지 않나」라는 물음에 답하는 글을 쓰려는 사람이 가장 먼저 읽을 문헌이다.