A Nontrivial Lower Bound for an NP Problem on Automata
From MaRDI portal
Publication:3477958
DOI10.1137/0219028zbMath0699.68062OpenAlexW2082154422MaRDI QIDQ3477958
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219028
Turing machineNP-complete problemrandom access machinelinear time reductionspectrum of a first-order sentenceIncompletely Specified Automatareduction of automata
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (6)
Algebraic and logical characterizations of deterministic linear time classes ⋮ Graph properties checkable in linear time in the number of vertices ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Sorting, linear time and the satisfiability problem ⋮ Exact complexity of problems of incompletely specified automata ⋮ Linear time and the power of one first-order universal quantifier
This page was built for publication: A Nontrivial Lower Bound for an NP Problem on Automata
