Completeness for nondeterministic complexity classes
- 1 December 1991
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 24 (1) , 179-200
- https://doi.org/10.1007/bf02090397
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Nondeterministic Space is Closed under ComplementationSIAM Journal on Computing, 1988
- A comparison of polynomial time completeness notionsTheoretical Computer Science, 1987
- Optimal approximations of complete setsPublished by Springer Nature ,1986
- On log-tape isomorphisms of complete setsTheoretical Computer Science, 1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971