Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$

Abstract

We show that the problem of determining the feasibility of quadratic systems over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.

arXiv commentThis was an early and insufficiently verified attempt. Errors affecting the main results were later identified, and the manuscript has been withdrawn

References in corpus (1)

• Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP