Classes of bounded nondeterminism

DOI10.1007/BF02090764zbMath0692.68029OpenAlexW1985250585MaRDI QIDQ3034815

Jacobo Toran, Josep Diaz

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090764

zbMATH Keywords

nondeterminismreducibilitiespolynomial-time machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On problems with short certificates, Resource-bounded kolmogorov complexity revisited, Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations, On helping by parity-like languages, On fixed-parameter tractability and approximability of NP optimization problems, On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata, On log-time alternating Turing machines of alternation depth k, Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines., Fault-tolerance and complexity (Extended abstract), The complexity of manipulative attacks in nearly single-peaked electorates, On quasilinear-time complexity theory, Computing functions with parallel queries to NP, Molecular computing, bounded nondeterminism, and efficient recursion, Monotone Boolean dualization is in co-NP\([\log^{2}n\).], The inapproximability of non-NP-hard optimization problems., The minimum equivalent DNF problem and shortest implicants

Cites Work

• Unnamed Item
• Unnamed Item
• Robust algorithms: a different approach to oracles
• On helping by robust oracle machines
• Relative complexity of checking and evaluating
• Complete problems for deterministic polynomial time
• Refining Nondeterminism in Relativizations of Complexity Classes
• Immunity, Relativizations, and Nondeterminism
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computational Complexity of Probabilistic Turing Machines
• Tally languages and complexity classes