부분 결과서지만 확인
Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisStephen R. Mahaney · 1982Journal of Computer and System Sciences 25(2), 130–143쪽 (1982) · 학회 발표 FOCS 1980 (21st Annual Symposium on Foundations of Computer Science), 54–60쪽희소한 NP-완전 집합이 있으면 P = NP 라는 Mahaney 정리의 출전으로 널리 인용된다. Berman 과 Hartmanis 가 물은 것(희소 집합은 NP-완전일 수 없는가)에 「P ≠ NP 라면 그렇다」로 답한 결과다. NP-완전 문제는 예 인스턴스가 드물 수 없다는 구조적 사실을 인용할 때 쓴다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 서지를 확인했다(본문은 열지 못함).