The NP-completeness column: An ongoing guide
- 3 September 1992
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 13 (3) , 502-524
- https://doi.org/10.1016/0196-6774(92)90052-e
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- Are there interactive protocols for co-NP languages?Information Processing Letters, 1988
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- AlternationJournal of the ACM, 1981
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976