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

《Computers and Intractability: A Guide to the Theory of NP-Completeness》는 NP-완전 문제를 처음 다룬 전산학의 고전이다. 마이클 개리와 데이비드 S. 존슨이 함께 지은 책으로 1979년에 출판되었다. 이 책은 수많은 논문에 자주 인용되는데, 주로 어떤 문제가 NP-완전임을 보이는 원 출처로서 인용된다. 비록 PCP 등 최근에 나온 주제를 다루지 않는 등 다소 오래되었다는 단점은 있으나, 전산학의 고전으로서 가치가 있는 책으로 2000년대 들어서도 계속 출판되고 있다.

이 책의 부록에는 당시 알려졌던 주요 NP-완전 문제(PSPACE-완전이거나 더 어려운 문제도 있다) 수백 개의 목록이 포함되어 있다. 이 목록은 아주 유명하여 전산학자들이 가끔 참고하기도 하고, 이후 보충된 NP-완전 문제들의 목록도 주로 이 목록의 형식을 따르고 있다.

2006년 9월 조사에 따르면 CiteSeer에서 이 책이 전산학 논문 인용 횟수 1위를 기록했다.