Garey and Johnson: Computers and Intractability
E679895
"Garey and Johnson: Computers and Intractability" is a foundational textbook in theoretical computer science that systematically develops the theory of NP-completeness and computational complexity.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Computers and Intractability: A Guide to the Theory of NP-Completeness | 1 |
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
book
ⓘ
textbook ⓘ theoretical computer science literature ⓘ |
| author |
David S. Johnson
NERFINISHED
ⓘ
Michael R. Garey NERFINISHED ⓘ |
| canonicalAbbreviation | G&J NERFINISHED ⓘ |
| citationFrequency | high ⓘ |
| countryOfPublication |
United States of America
ⓘ
surface form:
United States
|
| coversConcept |
NP class
ⓘ
NP-complete problems ⓘ NP-hard problems ⓘ P class ⓘ polynomial-time reduction ⓘ reduction between decision problems ⓘ |
| field | computer science ⓘ |
| focus | worst-case complexity ⓘ |
| hasSection |
catalog of NP-complete problems
ⓘ
introduction to computational complexity ⓘ techniques for proving NP-completeness ⓘ |
| influenced |
computer science education
ⓘ
design and analysis of algorithms ⓘ research in computational complexity theory ⓘ |
| language | English ⓘ |
| notableFor |
comprehensive catalog of NP-complete problems
ⓘ
formalization of polynomial-time reductions ⓘ systematic development of NP-completeness theory ⓘ |
| publicationYear | 1979 ⓘ |
| publisher | W. H. Freeman and Company NERFINISHED ⓘ |
| relatedTo |
Cook–Levin theorem
NERFINISHED
ⓘ
Karp’s 21 NP-complete problems NERFINISHED ⓘ P versus NP problem NERFINISHED ⓘ |
| shortTitle | Garey and Johnson NERFINISHED ⓘ |
| status | classic in theoretical computer science ⓘ |
| subfield |
computational complexity
ⓘ
theoretical computer science ⓘ |
| subject |
NP-completeness
NERFINISHED
ⓘ
P versus NP NERFINISHED ⓘ algorithmic intractability ⓘ complexity classes ⓘ computational complexity theory ⓘ decision problems ⓘ reduction techniques ⓘ |
| timeComplexityModel | Turing machine model ⓘ |
| typicalCourseUsage |
complexity theory courses
ⓘ
theory of computation courses ⓘ |
| usedAs |
graduate-level textbook
ⓘ
reference work ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Computers and Intractability: A Guide to the Theory of NP-Completeness