scientific article; zbMATH DE number 1332665
From MaRDI portal
Publication:4259986
DOI10.4086/cjtcs.1997.001zbMath0924.68080OpenAlexW4249409086MaRDI QIDQ4259986
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.
Related Items
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.