접근서지만 확인
On Isomorphisms and Density of NP and Other Complete SetsLeonard Berman, Juris Hartmanis · 1977SIAM Journal on Computing 6(2), 305–322쪽 (1977) · 학회 발표 STOC 1976 (Proceedings of the 8th Annual ACM Symposium on Theory of Computing), 30–40쪽알려진 NP-완전 집합이 모두 다항 시간 동형임을 보이고, 모든 NP-완전 집합이 그렇다면 P ≠ NP 임을 밝힌 논문이다. 「모든 NP-완전 집합은 서로 다항 시간 동형이다」라는 동형 추측의 출전이다. 추측이 참이면 희소한 NP-완전 집합이 없다는 귀결도 여기서 나온다. NP-완전 문제들의 구조에서 P ≠ NP 로 가려는 접근을 다루는 글에 필요하다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.