Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over C, R, and Z
Ali Çivril
所有作者
Ali Çivril
文献摘要
We show that the problem of determining the feasibility of quadratic systems over C, R, and Z requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.