Classes of bounded nondeterminism
From MaRDI portal
Recommendations
Cites work
- Complete problems for deterministic polynomial time
- Computational Complexity of Probabilistic Turing Machines
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3594673 (Why is no real title available?)
- Immunity, Relativizations, and Nondeterminism
- On helping by robust oracle machines
- On the Structure of Polynomial Time Reducibility
- Refining Nondeterminism in Relativizations of Complexity Classes
- Relative complexity of checking and evaluating
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Robust algorithms: a different approach to oracles
- Tally languages and complexity classes
Cited in
(24)- On problems with short certificates
- On helping by parity-like languages
- On fixed-parameter tractability and approximability of NP optimization problems
- A representable approach to finite nondeterminism
- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- The minimum equivalent DNF problem and shortest implicants
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- The inapproximability of non-NP-hard optimization problems.
- scientific article; zbMATH DE number 4045156 (Why is no real title available?)
- scientific article; zbMATH DE number 17527 (Why is no real title available?)
- scientific article; zbMATH DE number 176517 (Why is no real title available?)
- Nondeterminism within $P^ * $
- Unbounded Non-determinism in CSP
- Molecular computing, bounded nondeterminism, and efficient recursion
- Fault-tolerance and complexity (extended abstract)
- The complexity of manipulative attacks in nearly single-peaked electorates
- Resource-bounded Kolmogorov complexity revisited
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
- On log-time alternating Turing machines of alternation depth k
- On quasilinear-time complexity theory
- Computing functions with parallel queries to NP
- The logics for the complexity classes with limited non-determinism
This page was built for publication: Classes of bounded nondeterminism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034815)
