A Natural NP-Complete Problem with a Nontrivial Lower Bound
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 6520244
- A simplified NP-complete satisfiability problem
- scientific article; zbMATH DE number 2156275
- scientific article; zbMATH DE number 503394
- A Nontrivial Lower Bound for an NP Problem on Automata
- All natural NP-complete problems have average-case complete versions
- NP-completeness of a combinator optimization problem
- STACS 2004
- scientific article; zbMATH DE number 3874957
- An NP-complete number-theoretic problem
Cited in
(13)- On the bounded version of Hilbert's tenth problem
- Sorting, linear time and the satisfiability problem
- A nonasymptotic lower time bound for a strictly bounded second-order arithmetic
- One unary function says less than two in existential second order logic
- scientific article; zbMATH DE number 6520244 (Why is no real title available?)
- scientific article; zbMATH DE number 4170888 (Why is no real title available?)
- scientific article; zbMATH DE number 5320331 (Why is no real title available?)
- NP-Completeness of the Direct Energy Barrier Problem without Pseudoknots
- Fifty years of the spectrum problem: survey and new results
- Algebraic and logical characterizations of deterministic linear time classes
- NP-completeness of the energy barrier problem without pseudoknots and temporary arcs
- scientific article; zbMATH DE number 958366 (Why is no real title available?)
- First-order spectra with one variable
This page was built for publication: A Natural NP-Complete Problem with a Nontrivial Lower Bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3796747)
