scientific article; zbMATH DE number 1332665

DOI10.4086/CJTCS.1997.001MaRDI QIDQ4259986zbMATH OpenOpenAlexFDO

Authors Joe Kilian, Uriel Feige

Publication date 8 September 1999

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4086/cjtcs.1997.001

zbMATH Keywords

nondeterministic computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Nondeterminism within $P^ * $
• scientific article; zbMATH DE number 176517
• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
• ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM

Cited in

(15)

• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
• On the possibilities and limitations of pseudodeterministic algorithms
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• The inapproximability of non-NP-hard optimization problems.
• Nondeterminism within $P^ * $
• Open problems around exact algorithms
• Tight lower bounds for certain parameterized NP-hard problems
• A note on width-parameterized SAT: an exact machine-model characterization
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• Fixed-parameter approximation: conceptual framework and approximability results
• Strong computational lower bounds via parameterized complexity
• scientific article; zbMATH DE number 176517 (Why is no real title available?)
• Improved simulation of nondeterministic Turing machines
• On limitations of structured (deterministic) DNNFs
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)

This page was built for publication:

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