On NP-completeness for linear machines
From MaRDI portal
Publication:1368835
DOI10.1006/jcom.1997.0444zbMath0888.68059OpenAlexW2156565475MaRDI QIDQ1368835
Publication date: 1 October 1997
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcom.1997.0444
Related Items
A topological view on algebraic computation models ⋮ Computation over algebraic structures and a classification of undecidable problems ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ On the computational structure of the connected components of a hard problem
Cites Work
- Unnamed Item
- A survey on real structural complexity theory
- Real number models under various sets of operations
- Separation of complexity classes in Koiran's weak model
- Computing over the reals with addition and order
- On digital nondeterminism
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
