scientific article; zbMATH DE number 1332665
From MaRDI portal
Publication:4259986
DOI10.4086/CJTCS.1997.001zbMATH Open0924.68080OpenAlexW4249409086MaRDI QIDQ4259986FDOQ4259986
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
Title of this publication is not available (Why is that?)
Recommendations
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.
- Nondeterminism within $P^ * $
- The inapproximability of non-NP-hard optimization problems.
- 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
- Title not available (Why is that?)
- 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)
