A note on a \(P \neq NP\) result for a restricted class of real machines

DOI10.1016/0885-064X(92)90007-XzbMath0758.68030MaRDI QIDQ1203647

Klaus Meer

Publication date: 22 February 1993

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

Blum-Shub-Smale machinesequality-testslinear computations

Mathematics Subject Classification ID

Related Items (15)

Complexity and dimension ⋮ Separation of complexity classes in Koiran's weak model ⋮ Computing over the reals with addition and order ⋮ On the P-NP problem over real matrix rings ⋮ Elimination of constants from machines over algebraically closed fields ⋮ Real data-integer solution problems within the Blum-Shub-Smale computational model ⋮ On NC-real complexity classes for additive circuits and their relations with NC ⋮ Generalization of the subset sum problem and cubic forms ⋮ On sparseness and Turing reducibility over the reals ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ The P-DNP problem for infinite Abelian groups ⋮ On sparseness, reducibilities, and complexity ⋮ On digital nondeterminism ⋮ Transfer theorems via sign conditions ⋮ On the computational structure of the connected components of a hard problem

Cites Work

• On the complexity of computations under varying sets of primitives
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: A note on a \(P \neq NP\) result for a restricted class of real machines