부분 결과서지만 확인
Every Prime Has a Succinct CertificateVaughan R. Pratt · 1975SIAM Journal on Computing 4(3), 214–220쪽 (1975)어떤 수가 소수라는 사실에도 자릿수의 다항식 길이인 짧은 증명서가 있음을 보인 논문이다. 합성수의 증명서(약수)는 자명하므로, 이로써 소수 판정은 NP 와 coNP 양쪽에 들게 되었다. 「NP ∩ coNP 에 있지만 P 인지 모르던 문제」의 고전적인 예로, 2004년에 P 임이 밝혀지기까지(aks-2004)의 역사를 적는 글에 필요하다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자·권호·쪽을 확인하고 같은 기록의 초록을 읽었다.