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

AbstractWe 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 ResultTheorem 4.1. P_alg = NP_alg