Computers and Intractability: A Guide to the Theory of NP-Completeness

1. 개요

"Computers and Intractability: A Guide to the Theory of NP-Completeness"는 NP-완전성 이론에 대한 안내서로, NP-완전 문제와 P-NP 문제 간의 관계를 다룬다. 이 책은 NP-완전인지, P에 속하는지, 또는 둘 다 아닌지 알려지지 않은 여러 문제들을 제시하고 있으며, 그래프 동형 사상, 부분 그래프 준동형 사상, 그래프 종수, 현 완성, 변 채색, 스패닝 트리 패리티 문제, 차원, 우선 순위 제약 3-프로세서 스케줄링, 선형 계획법, 완전 단일 모듈성, 합성수, 최소 가중치 삼각 분할 등이 그 예시이다. 출간 직후 이 책은 컴퓨터 과학 분야의 저명한 연구자들로부터 긍정적인 평가를 받았으며, NP-완전성에 대한 철저하고 명확하며 실용적인 해설로 인정받았다.

2. NP-완전 문제와 미해결 문제

계산 복잡도 이론에서 NP-완전 문제는 P-NP 문제와 더불어 핵심적인 연구 주제이다. "Computers and Intractability: A Guide to the Theory of NP-Completeness"의 부록에서는 출판 당시 NP-완전인지 P에 속하는지, 혹은 그 중간 상태인지 명확히 밝혀지지 않은 여러 중요한 계산 문제들을 목록으로 제시하였다. 이 목록은 당시 계산 복잡도 이론 분야의 주요 미해결 과제들을 보여주었으며, 이후 관련 연구 방향 설정에 영향을 미쳤다.

2.1. 개리 & 존슨의 미해결 문제 목록

이 책의 부록에는 NP-완전인지 P에 속하는지, 혹은 둘 다 아닌지 알려지지 않은 중요한 계산 문제들의 목록이 실려 있다. 이 목록은 출판 당시 계산 복잡도 이론 분야의 주요 미해결 과제들을 제시하며, 이후 관련 연구 방향에 영향을 미쳤다. 각 문제에 대한 구체적인 내용과 현재까지 알려진 상태는 아래 하위 섹션들에서 자세히 설명한다.

2.1.1. 그래프 관련 문제

이 책의 부록에는 NP-완전인지 P에 속하는지, 혹은 둘 다 아닌지 알려지지 않은 문제들이 실려 있다. 그중 그래프와 관련된 주요 문제들은 다음과 같다.

* 그래프 동형 사상 문제: 이 문제는 NP에 속하는 것으로 알려져 있지만, NP-완전인지 여부는 아직 밝혀지지 않았다.
* 부분 그래프 준동형 사상 (고정된 그래프 H에 대해)
* 그래프 종수
* 현 그래프 완성
* 색 지수

이 문제들은 계산 복잡도 이론에서 중요한 위치를 차지하며, 아직 해결되지 않은 상태로 남아 있다.

2.1.2. 순서 및 스케줄링 문제

이 책의 부록에는 NP-완전인지 P에 속하는지 (또는 둘 다 아닌지) 알려지지 않은 문제들이 실려 있다. 그중 순서 및 스케줄링과 관련된 문제들은 다음과 같다.

* 스패닝 트리 패리티 문제
* 부분 순서 차원
* 우선 순위 제약 3-프로세서 스케줄링 (이 문제는 2016년까지도 미해결 상태였다.)

2.1.3. 선형 계획법 및 정수론 관련 문제

이 책의 부록에는 NP-완전인지 P에 속하는지 (또는 둘 다 아닌지) 알려지지 않은 문제들이 실려 있다. 이 중 선형 계획법 및 정수론과 관련된 문제들은 다음과 같다.

* [[선형 계획법]]: 이 문제의 복잡도 상태는 당시 알려지지 않았다.
* 완전 단일 모듈성
* [[AKS 소수성 검사|합성수]]: 합성수 검사는 P에 속하는 것으로 알려져 있지만, 이와 밀접하게 관련된 정수 인수분해 문제의 복잡성은 여전히 미해결 상태로 남아 있다.

2.1.4. 기타 문제

이 책의 부록에는 NP-완전인지 P에 속하는지 (또는 둘 다 아닌지) 알려지지 않은 여러 문제들이 실려 있다. 해당 문제들은 다음과 같다.

* 그래프 동형 사상: 이 문제는 NP에 속하는 것으로 알려져 있지만, NP-완전인지 여부는 알려져 있지 않다.
* 부분 그래프 준동형 사상 (고정된 그래프 H에 대해)
* 그래프 종수
* 현 그래프 완성
* 색 지수
* 스패닝 트리 패리티 문제
* 부분 순서 차원
* 우선 순위 제약 3-프로세서 스케줄링: 이 문제는 2016년까지도 미해결 상태였다.
* 선형 계획법
* 완전 단일 모듈성
* 합성수: 합성수 검사는 P에 속하는 것으로 알려져 있다. 하지만 이와 밀접하게 관련된 정수 인수분해 문제의 복잡성은 여전히 미해결 상태로 남아 있다.
* 최소 길이 삼각 분할: 이 문제는 NP-hard인 것으로 알려져 있지만, NP에 속하는지는 알려져 있지 않다.

3. "Computers and Intractability" 서적에 대한 평가

이 책은 출간 이후 이론 컴퓨터 과학 분야에서 중요한 저작으로 꾸준히 인정받고 있다. 여러 저명한 연구자들이 이 책의 명확성, 철저함, 실용성을 높이 평가했으며, 특히 NP-완전성 문제를 다루는 연구자들에게 필독서로 추천되었다. 책의 부록에 담긴 방대한 NP-난해 문제 목록 역시 연구의 시작점으로서 큰 가치를 지닌 것으로 평가받는다. 시간이 흘러도 그 중요성은 여전하여, 계산 복잡도 이론 분야의 고전이자 필수적인 참고 자료로 자리매김했다.

3.1. 학계의 평가

출간 직후 이 책은 이론 컴퓨터 과학 분야의 저명한 연구자들로부터 긍정적인 평가를 받았다.

로널드 V. 북(Ronald V. Book)은 서평에서 "NP-완전성에 대해 배우고 싶은 모든 사람"에게 이 책을 추천하며, 300개 이상의 NP-난해한 계산 문제를 담은 부록이 "매우 유용하다"고 명시적으로 언급했다. 그는 "컴퓨터 과학에는 이 책과 같은 책이 더 많이 필요하다"고 결론지었다.

해리 R. 루이스(Harry R. Lewis)는 저자들의 수학적 문체를 칭찬하며 "개리(Garey)와 존슨(Johnson)의 책은 NP-완전성에 대한 철저하고 명확하며 실용적인 해설이다. 여러 면에서 이 주제에 대한 더 나은 설명은 상상하기 어렵다"고 말했다. 또한 그는 부록을 "독창적"이며 "새로운 문제를 NP-완전성으로 증명하려는 시도의 시작점"으로 평가했다.

책이 출간된 지 23년 후, 학술 저널 전산 이론 논문집(Transactions on Computational Theory)의 편집장인 랜스 포트노(Lance Fortnow)는 다음과 같이 평가했다. "나는 개리(Garey)와 존슨(Johnson)의 책을 내 서재에서 가장 중요한 책으로 여긴다. 모든 컴퓨터 과학자는 이 책을 서가에 꽂아두어야 한다. [...] 개리(Garey)와 존슨(Johnson)의 책은 내가 본 계산 복잡성에 대한 최고의 입문서이다."