On the Amount of Nondeterminism and the Power of Verifying

DOI10.1137/S0097539793258295zbMATH Open0870.68062MaRDI QIDQ4337644FDOQ4337644

Authors: Liming Cai, Jianer Chen 

Publication date: 26 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Nondeterminism within $P^ * $
• scientific article
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• On Models of a Nondeterministic Computation

zbMATH Keywords

computational complexitycomputational optimizationnondeterminismcomplete languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (16)

• Simplifying the weft hierarchy
• The inapproximability of non-NP-hard optimization problems.
• Context-dependent nondeterminism for pushdown automata
• A fixed-parameter-tractable algorithm for set packing
• The intractability of computing the Hamming distance
• Deterministic FOIES are strictly weaker
• The minimum equivalent DNF problem and shortest implicants
• Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
• Using Nondeterminism to Amplify Hardness
• Fixed-parameter approximation: conceptual framework and approximability results
• Bounded fixed-parameter tractability and reducibility
• Parameterized complexity of three edge contraction problems with degree constraints
• In memoriam Chandra Kintala
• Deterministic unimodularity certification
• On the power of deterministic reductions to C=P
• Parameterized complexity and subexponential-time computability

This page was built for publication: On the Amount of Nondeterminism and the Power of Verifying

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337644)