P = NP Reducing 3-SAT to Degree-3 Polynomial Systems over F₂ 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 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