Nondeterminism within $P^ * $
- 1 June 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 22 (3), 560-572
- https://doi.org/10.1137/0222038
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Classes of bounded nondeterminismTheory of Computing Systems, 1990
- The Complexity of Very Simple Boolean Formulas with ApplicationsSIAM Journal on Computing, 1990
- Complexity classes with complete problems between P and NP-CLecture Notes in Computer Science, 1989
- Nearly linear timeLecture Notes in Computer Science, 1989
- Relativized alternation and space-bounded computationJournal of Computer and System Sciences, 1988
- Short propositional formulas represent nondeterministic computationsInformation Processing Letters, 1988
- research-articleThe Journal of Symbolic Logic, 1986
- Some combinatorial game problems require Ω(
n
k
) timeJournal of the ACM, 1984
- Refining Nondeterminism in Relativized Polynomial-Time Bounded ComputationsSIAM Journal on Computing, 1980
- Satisfiability Is Quasilinear Complete in NQLJournal of the ACM, 1978