P = NP Reducing 3-SAT to Degree-3 Polynomial Systems over F₂ 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 F₂ 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 F₂, exploiting the bounded degree and field equations. Since 3-SAT is NP-complete, it follows that P = NP.
Fields of Study & Subjects
Polynomial and algebraic computation
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Publication details
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Preprint