Hierarchies of complete problems
- 1 March 1976
- journal article
- Published by Springer Science and Business Media LLC in Acta Informatica
- Vol. 6 (1), 77-88
- https://doi.org/10.1007/bf00263744
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- A combinatorial problem which is complete in polynomial spacePublished by Association for Computing Machinery (ACM) ,1975
- Computational complexity of probabilistic Turing machinesPublished by Association for Computing Machinery (ACM) ,1974
- Some simplified NP-complete problemsPublished by Association for Computing Machinery (ACM) ,1974
- Complete problems for deterministic polynomial timePublished by Association for Computing Machinery (ACM) ,1974
- On some direct encodings of nondeterministic Turing machines operating in polynomial time into p-complete problemsACM SIGACT News, 1974
- An observation on time-storage trade offPublished by Association for Computing Machinery (ACM) ,1973
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Mathematical GamesScientific American, 1970
- Checking automata and one-way stack languagesJournal of Computer and System Sciences, 1969