Scheme-theoretic Approach to Computational Complexity II. The Separation\n of P and NP over \ℂ, \ℝ, and \ℤ

2021/07/06 by Ali Çivril, Çivril, Ali · 1 citation
Computer Science · Mathematics · #Algorithm #Coding theory and cryptography #Combinatorics #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computation #Computational complexity theory #Discrete mathematics #Exponential function #Geometry #Mathematical analysis #Mathematical physics #Mathematics #Physics #Quadratic equation #Quantum Computing Algorithms and Architecture #Scheme (mathematics) #cs.CC #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2107.07387

openalex publication_date 2021/07/06 · openalex created_date 2022/07/25 · openalex updated_date 2026/08/05

Abstract

We show that the problem of determining the feasibility of quadratic systems\nover \ℂ, \ℝ, and \ℤ requires exponential time.\nThis separates P and NP over these fields/rings in the BCSS model of\ncomputation.\n

Cited by

• Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation

Related

• Scheme-theoretic Approach to Computational Complexity I. The Separation\n of P and NP
• The Problem of Computational Complexity
• Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy
• Some Speed-Ups and Speed Limits for Real Algebraic Geometry
• P is a proper subset of NP