The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(92)90052-EzbMath0786.68035MaRDI QIDQ5966695

David S. Johnson

Publication date: 16 January 1993

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

\(NP\)-completeness\(NP\)-hard problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Probabilistically checkable proofs and their consequences for approximation algorithms, Deciding 3-colourability in less than O(1.415n) steps, On approximating the longest path in a graph