A Natural NP-Complete Problem with a Nontrivial Lower Bound

DOI10.1137/0217050zbMath0651.68053OpenAlexW2057894153MaRDI QIDQ3796747

Etienne Grandjean

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217050

zbMATH Keywords

NP-complete problemslower boundslinear time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (5)

One unary function says less than two in existential second order logic ⋮ Algebraic and logical characterizations of deterministic linear time classes ⋮ First-order spectra with one variable ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Sorting, linear time and the satisfiability problem

This page was built for publication: A Natural NP-Complete Problem with a Nontrivial Lower Bound