scientific article; zbMATH DE number 1332665

DOI10.4086/cjtcs.1997.001zbMath0924.68080OpenAlexW4249409086MaRDI QIDQ4259986

Joe Kilian

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: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

nondeterministic computation

Mathematics Subject Classification ID

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

Related Items (9)

Fixed-parameter approximation: conceptual framework and approximability results ⋮ Strong computational lower bounds via parameterized complexity ⋮ On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\) ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ Open problems around exact algorithms ⋮ A note on width-parameterized SAT: an exact machine-model characterization ⋮ Improved simulation of nondeterministic Turing machines ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ The inapproximability of non-NP-hard optimization problems.

This page was built for publication: