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

2021/07/06 by Ali Çivril, Çivril, Ali · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Computability, Logic, AI Algorithms #Computational complexity theory #Computational geometry #Computational model #Computer science #Discrete mathematics #Graph Labeling and Dimension Problems #Mathematical analysis #Mathematical optimization #Mathematics #Moduli #Physics #Quantum mechanics #Scheme (mathematics) #Theoretical computer science #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2107.07386

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

Abstract

We lay the foundations of a new theory for algorithms and computational\ncomplexity by parameterizing the instances of a computational problem as a\nmoduli scheme. Considering the geometry of the scheme associated to 3-SAT, we\nseparate P and NP. In particular, we show that no deterministic algorithm can\nsolve textsf3-SAT in time less than 1.296839ⁿ in the worst case.\n

Cited by

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

Related

• Scheme-Theoretic Approach to Computational Complexity. III. SETH
• Scheme-theoretic Approach to Computational Complexity II. The Separation\n of P and NP over \ℂ, \ℝ, and \ℤ
• The Problem of Computational Complexity
• Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
• Algorithm that Solves 3-SAT in Polynomial Time