맨위로가기

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

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 컴퓨터 과학 책 - Introduction to Algorithms
    Introduction to Algorithms는 코멘, 리서슨, 라이베스트, 스타인이 저술한 알고리즘 분야의 교재이자 참고 자료로, 여러 판본을 거쳐 내용이 갱신 및 보완되었으며 컴퓨터 과학, 공학, 수학 전공 학생들과 알고리즘에 관심 있는 사람들에게 유용하다.
  • 컴퓨터 과학 책 - 의사소통의 수학적 이론
    의사소통의 수학적 이론은 1948년 발표된 논문으로, 정보원, 송신기, 통신로, 수신기, 목적지 등 통신 기본 요소를 제시하고 정보량, 비트, 채널 용량 등의 개념을 도입했으며, 섀넌-파노 부호화 기법을 개발했다.
  • 1979년 책 - 성공회 기도서
    성공회 기도서는 잉글랜드 종교 개혁 과정에서 가톨릭 교회의 성무일도에서 파생되어 예배, 기도, 성례 등의 절차를 담은 규칙서로, 영어 예배와 성서학 및 고전문헌학 발달에 영향을 미쳤으며 대한성공회에서는 '성공회 기도서' 또는 '기도서'라는 명칭으로 사용된다.
  • 1979년 책 - 환단고기
    환단고기는 환국, 배달국, 고조선 등 고대 국가의 역사를 다룬다고 주장하며, 1911년에 간행되었다고 알려졌지만, 역사학계에서는 위서로 판단한다.
Computers and Intractability: A Guide to the Theory of NP-Completeness - [서적]에 관한 문서
서지 정보
제목컴퓨터와 난해성: NP-완전성 이론 안내서
원제Computers and Intractability: A Guide to the Theory of NP-Completeness
저자마이클 R. 게리와 데이비드 S. 존슨
삽화가해당사항 없음
표지 미술가해당사항 없음
국가미국
언어영어
시리즈수학 과학 서적 시리즈
주제컴퓨터 과학
장르교재
출판사W. H. 프리먼 앤 컴퍼니
출판일1979년
미디어 유형인쇄
페이지 수x+338
ISBN0-7167-1045-5
Dewey 십진분류법519.4
의회 도서관 통제 번호QA76.6 .G35
OCLC247570676
선행 작품해당사항 없음
후행 작품해당사항 없음

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에 속하는지 (또는 둘 다 아닌지) 알려지지 않은 문제들이 실려 있다. 이 중 선형 계획법 및 정수론과 관련된 문제들은 다음과 같다.

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

2. 1. 4. 기타 문제

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

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

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

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

3. 1. 학계의 평가

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

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

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

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

참조

[1] 서적 Computers and Intractability: A Guide to the Theory of NP-Completeness W. H. Freeman and Co.
[2] 간행물 Computers and Intractability: A Guide to the Theory of NP-Completeness, book review
[3] 웹사이트 Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity) http://citeseer.ist.[...] 2007-11-03
[4] 간행물 The NP-Completeness of Edge-Coloring 1981-11
[5] 서적 Algebraic Methods in Graph Theory, Volume II (Colloquium Szeged, 1978) North-Holland
[6] conference Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width Springer-Verlag
[7] 간행물 Decomposition of regular matroids http://dml.cz/bitstr[...] 1980-06
[8] citation Minimum-weight triangulation is NP-hard
[9] 문서 Review: Computers and intractability: A guide to the theory of NP-completeness https://www.ams.org/[...]
[10] 간행물 Review: Computers and intractability: A guide to the theory of NP-completeness https://www.jstor.or[...]
[11] 문서 Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. http://blog.computat[...] 2002-08-30
[12] 웹인용 Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity) http://citeseer.ist.[...] 2008-05-13


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com