P = NP Reducing 3-SAT to Degree-3 Polynomial Systems over $\mathbb{F}_2$ via Direct Operator Substitution and Polynomial-Time Resolution by a CAS

Read full text
Authors: Kaoru Aguilera Katayama
Cited by: 0

Abstract

We present a deterministic polynomial-time reduction from 3-SAT to the problem of deciding whether a system of polynomial equations of degree at most $3$ over $\mathbb{F}_2$ has a solution. The restriction to 3-SAT guarantees that every polynomial produced by the direct substitution map has degree exactly $3$ or less, yielding a system that is maximally efficient for resolution by a Computer Algebra System (CAS). We establish that the CAS solves this degree-bounded system in polynomial time via Gröbner basis computation over $\mathbb{F}_2$, exploiting the bounded degree and field equations. Since 3-SAT is NP-complete, it follows that $\mathrm{P} = \mathrm{NP}$.

Fields of Study & Subjects

Polynomial and algebraic computation Complexity and Algorithms in Graphs Advanced Graph Theory Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
7 March 2026
Language
EN
Document type
Preprint