On the Algebraic Identity of Verification and Construction A Note on Bounded Arithmetic

Read full text
Authors: Christopher Pompetzki
Cited by: 0

Abstract

We define complexity classes P_alg and NP_alg in purely algebraic terms within bounded arithmetic, using a characterization of polynomial functions as the smallest class closed under addition and multiplication from generators {0, 1, n}. We show that P_alg= NP_alg as a syntactic fact: bounded existential quantification does not enlarge the class of bounded formulas. The separation between P and NP in computational complexity theory is thereby identified as arising from execution semantics imported into arithmetic, not from arithmetic itself.Main Result:TheoremP_alg = NP_alg

Fields of Study & Subjects

Computability Logic AI Algorithms programming and type systems Complexity and Algorithms in Graphs

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
12 January 2026