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
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