The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(84)90022-1zbMath0547.68048OpenAlexW4236796471MaRDI QIDQ5896449

David S. Johnson

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90022-1

zbMATH Keywords

randomizationprobabilistic Turing machinecomplexity classNP- completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem books (00A07)

Related Items

Classifying the computational complexity of problems, Factoring polynomials using fewer random bits, Scheduling with neural networks -- the case of the Hubble Space Telescope, A Rigorous Time Bound for Factoring Integers