On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture

DOI10.1006/jcom.2000.0568zbMath0974.68066WikidataQ122929201 ScholiaQ122929201MaRDI QIDQ5938580

Gregorio Malajovich

Publication date: 12 December 2001

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

Full work available at URL: https://doi.org/10.1006/jcom.2000.0568

zbMATH Keywords

NP-completeness

Mathematics Subject Classification ID

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

Related Items

On the Order of Power Series and the Sum of Square Roots Problem

Cites Work

• A weak version of the Blum, Shub, and Smale model
• Factoring polynomials with rational coefficients
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• Computing over the reals with addition and order
• On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• Polynomial algorithms for linear programming over the algebraic numbers
• Computational complexity over the \(p\)-adic numbers
• Mathematical problems for the next century
• Computing over the reals with addition and order: Higher complexity classes
• Complexity of Bezout's Theorem I: Geometric Aspects
• On the Power of Real Turing Machines over Binary Inputs
• On weak and weighted computations over the real closure of \(\mathbb{Q}\)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item