컴퓨터 및 난해성

Computers and Intractability
컴퓨터와 난해성: NP-완전성 이론의 지침서
Garey, Johnson, Intractability, cover.jpg
작가마이클 R. 개리와 데이비드 S. 존슨
나라미국
언어영어
시리즈수학적 과학의 책 시리즈
제목컴퓨터 공학
장르.교과서
출판사W. H. 프리먼 앤 컴퍼니
발행일자
1979
매체형인쇄하다
페이지x+338
ISBN0-7167-1045-5
OCLC247570676
519.4
LC ClassQA76.6 .G35

컴퓨터 과학에서 보다 구체적으로 계산 복잡성 이론인 컴퓨터와 난해성: NP-완전성 이론의 지침서는 마이클 개리와 데이비드 S. 존슨이 쓴 교과서다.[1]이 책은 NP-완전성과 계산 난해성 이론에 관한 최초의 책이었다.[2]이 책에는 NP-완전한 문제의 철저한 개요를 제공하는 부록이 수록되어 있다(이 책의 후반 인쇄물에서 업데이트되었다).이 책은 PCP 정리 등 최근 전개된 내용을 다루지 않기 때문에 현재 어떤 면에서는 시대에 뒤떨어져 있다.그럼에도 불구하고 그것은 여전히 출판되고 있고 고전적인 것으로 간주되고 있다: 2006년 연구에서 CiteSeer 검색 엔진은 이 책을 컴퓨터 과학 문헌에서 가장 인용된 참고 문헌으로 열거했다.[3]

문제 열기

이 책의 또 다른 부록에는 NP-완성인지 P(또는 둘 다)인지 알 수 없는 문제가 수록되어 있다.(본래의 명칭과 함께) 문제는 다음과 같다.

  1. 그래프 이형성
    이 문제는 NP에 있는 것으로 알려져 있으나 NP 완성 여부는 알 수 없다.
  2. 하위 그래프 동형성(고정 그래프 H의 경우)
  3. 그래프속
  4. 화음 그래프 완성
  5. 색도 지수[4]
  6. 스패닝 트리 패리티 문제[5]
  7. 부분순차원
  8. 우선 순위가 제한된 3-프로세서 스케줄링
    이 문제는 2016년 현재도 열려 있다.[6]
  9. 선형 프로그래밍
  10. 총단일성[7]
  11. 합성수
    복합성 시험은 P에 있는 것으로 알려져 있지만, 밀접하게 관련된 정수 인수 문제의 복잡성은 여전히 열려 있다.
  12. 최소 길이 삼각측량[8]
    문제 12는 NP-hard로 알려져 있지만 NP에 있는지는 알 수 없다.

리셉션

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

그의 논평에서, Ronald V. Book은 이 책을 "NP-완전성의 주제에 대해 배우고자 하는 모든 사람"에게 추천하며, 그는 300개 이상의 NP-하드 계산 문제가 있는 "극히 유용한" 부록에 대해 명시적으로 언급하고 있다.그는 "컴퓨터 과학은 이와 같은 책이 더 많이 필요하다"고 결론짓는다.[9]

해리 R. 루이스는 저자들의 수학적인 산문을 칭찬한다: "게리와 존슨의 책은 NP-완전성의 철저하고 명확하며 실용적인 설명이다.많은 측면에서 그 주제에 대한 더 나은 처우를 상상하기는 어렵다."또한, 그는 부록이 "독특한" 것이며 "NP-완전성이라는 새로운 문제를 보여주려는 시도의 출발점"으로 간주한다.[10]

이 책이 나온 지 23년이 지난 후 랜스 포트노우 과학저널 컴퓨터 이론에 관한 거래의 편집장은 "나는 개리와 존슨이 내 사무실 책장에서 가장 중요한 책이라고 생각한다"고 말했다.모든 컴퓨터 과학자들도 이 책을 책꽂이에 올려 놓아야 해. [...] 개리와 존슨은 내가 본 컴퓨터 복잡성에 대한 최고의 소개를 가지고 있어."[11]

참고 항목

참조

  1. ^ 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.
  2. ^ 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.
  3. ^ "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". Retrieved 2007-11-03.
  4. ^ NP 완료:
  5. ^ P:
  6. ^ 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.
  7. ^ P:
  8. ^ NP 하드:
  9. ^ 로널드 5세책. 리뷰: 컴퓨터와 난해성: NP완전성 Bull 이론의 지침.아머. 수학.Soc. (N.S.), 3(2), 페이지 898–904, 1980.
  10. ^ 해리 R. Lewis, Review: 컴퓨터와 난해성: NP완전성 이론의 지침서, 기호논리학 저널, 제48(2), 페이지 498–500, 1983.
  11. ^ Lance Fortnow, Great Books: 컴퓨터와 난해성: Michael R에 의한 NP-완전성 이론의 지침서. 개리와 데이비드 S. 존슨.2002년 8월 30일, 계산 복잡성 블로그.