컴퓨터 및 난해성
Computers and Intractability![]() | |
작가 | 마이클 R. 개리와 데이비드 S. 존슨 |
---|---|
나라 | 미국 |
언어 | 영어 |
시리즈 | 수학적 과학의 책 시리즈 |
제목 | 컴퓨터 공학 |
장르. | 교과서 |
출판사 | W. H. 프리먼 앤 컴퍼니 |
발행일자 | 1979 |
매체형 | 인쇄하다 |
페이지 | x+338 |
ISBN | 0-7167-1045-5 |
OCLC | 247570676 |
519.4 | |
LC Class | QA76.6 .G35 |
컴퓨터 과학에서 보다 구체적으로 계산 복잡성 이론인 컴퓨터와 난해성: NP-완전성 이론의 지침서는 마이클 개리와 데이비드 S. 존슨이 쓴 교과서다.[1]이 책은 NP-완전성과 계산 난해성 이론에 관한 최초의 책이었다.[2]이 책에는 NP-완전한 문제의 철저한 개요를 제공하는 부록이 수록되어 있다(이 책의 후반 인쇄물에서 업데이트되었다).이 책은 PCP 정리 등 최근 전개된 내용을 다루지 않기 때문에 현재 어떤 면에서는 시대에 뒤떨어져 있다.그럼에도 불구하고 그것은 여전히 출판되고 있고 고전적인 것으로 간주되고 있다: 2006년 연구에서 CiteSeer 검색 엔진은 이 책을 컴퓨터 과학 문헌에서 가장 인용된 참고 문헌으로 열거했다.[3]
문제 열기
이 책의 또 다른 부록에는 NP-완성인지 P(또는 둘 다)인지 알 수 없는 문제가 수록되어 있다.(본래의 명칭과 함께) 문제는 다음과 같다.
- 그래프 이형성
- 이 문제는 NP에 있는 것으로 알려져 있으나 NP 완성 여부는 알 수 없다.
- 하위 그래프 동형성(고정 그래프 H의 경우)
- 그래프속
- 화음 그래프 완성
- 색도 지수[4]
- 스패닝 트리 패리티 문제[5]
- 부분순차원
- 우선 순위가 제한된 3-프로세서 스케줄링
- 이 문제는 2016년 현재도 열려 있다.[6]
- 선형 프로그래밍
- 총단일성[7]
- 합성수
- 복합성 시험은 P에 있는 것으로 알려져 있지만, 밀접하게 관련된 정수 인수 문제의 복잡성은 여전히 열려 있다.
- 최소 길이 삼각측량[8]
- 문제 12는 NP-hard로 알려져 있지만 NP에 있는지는 알 수 없다.
리셉션
이 책은 등장 직후 이론 컴퓨터 과학 분야에서 저명한 연구자들로부터 긍정적인 평가를 받았다.
그의 논평에서, Ronald V. Book은 이 책을 "NP-완전성의 주제에 대해 배우고자 하는 모든 사람"에게 추천하며, 그는 300개 이상의 NP-하드 계산 문제가 있는 "극히 유용한" 부록에 대해 명시적으로 언급하고 있다.그는 "컴퓨터 과학은 이와 같은 책이 더 많이 필요하다"고 결론짓는다.[9]
해리 R. 루이스는 저자들의 수학적인 산문을 칭찬한다: "게리와 존슨의 책은 NP-완전성의 철저하고 명확하며 실용적인 설명이다.많은 측면에서 그 주제에 대한 더 나은 처우를 상상하기는 어렵다."또한, 그는 부록이 "독특한" 것이며 "NP-완전성이라는 새로운 문제를 보여주려는 시도의 출발점"으로 간주한다.[10]
이 책이 나온 지 23년이 지난 후 랜스 포트노우 과학저널 컴퓨터 이론에 관한 거래의 편집장은 "나는 개리와 존슨이 내 사무실 책장에서 가장 중요한 책이라고 생각한다"고 말했다.모든 컴퓨터 과학자들도 이 책을 책꽂이에 올려 놓아야 해. [...] 개리와 존슨은 내가 본 컴퓨터 복잡성에 대한 최고의 소개를 가지고 있어."[11]
참고 항목
참조
- ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.
- ^ Juris Hartmanis (1982). "Computers and Intractability: A Guide to the Theory of NP-Completeness, book review". SIAM Review. 24 (1): 90–91. doi:10.1137/1024022. JSTOR 2029450.
- ^ "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". Retrieved 2007-11-03.
- ^ NP 완료:
- ^ P:
- ^ van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, Christian; Talmon, Nimrod; Woeginger, Gerhard J. (2016). "Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width". DOOR 2016: Discrete Optimization and Operations Research. Lecture Notes in Computer Science. Vol. 9869. Springer-Verlag. pp. 105–120. arXiv:1605.00901. doi:10.1007/978-3-319-44914-2_9.
- ^ P:
- ^ NP 하드:
- ^ 로널드 5세책. 리뷰: 컴퓨터와 난해성: NP완전성 Bull 이론의 지침.아머. 수학.Soc. (N.S.), 3(2), 페이지 898–904, 1980.
- ^ 해리 R. Lewis, Review: 컴퓨터와 난해성: NP완전성 이론의 지침서, 기호논리학 저널, 제48(2), 페이지 498–500, 1983.
- ^ Lance Fortnow, Great Books: 컴퓨터와 난해성: Michael R에 의한 NP-완전성 이론의 지침서. 개리와 데이비드 S. 존슨.2002년 8월 30일, 계산 복잡성 블로그.