On NP-completeness for linear machines

DOI10.1006/JCOM.1997.0444MaRDI QIDQ1368835zbMATH OpenOpenAlexFDO

Authors Christine Gaßner

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

zbMATH Keywords

Blum-Shub-Smale model of computationcomplexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computing over the reals with addition and order
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• scientific article; zbMATH DE number 515738
• On digital nondeterminism

Cites work

• A survey on real structural complexity theory
• Computing over the reals with addition and order
• scientific article; zbMATH DE number 503394 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On digital nondeterminism
• Real number models under various sets of operations
• Separation of complexity classes in Koiran's weak model

Cited in

(8)

• On the computational structure of the connected components of a hard problem
• A topological view on algebraic computation models
• Linear Time Algorithms and NP-Complete Problems
• Computation over algebraic structures and a classification of undecidable problems
• On digital nondeterminism
• On relativizations of the P =? NP question for several structures
• Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines
• Computing measure as a primitive operation in real number computation

This page was built for publication: On NP-completeness for linear machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1368835)