AI as a Statistical Verifier for NP Problems: Introducing the NP_p Complexity Class

The distinction between P and NP remains a fundamental open question in computational complexity. We introduce NP_p, a complexity class where problems can be verified by a polynomial-time probabilistic verifier with correctness probability at least p. Unlike NP, which assumes deterministic verification, NP_p extends verification into the probabilistic domain while remaining a subset of NP unless p = 1. We prove that NP_p is strictly larger than RP and BPP, and that as p approaches 1, NP_p collapses to NP. Building on this, we explore the implications of AI-driven verifiers, arguing that a Universal Artificial Learner (UAL) capable of refining its verification process into a deterministic polynomial-time solver would imply NP = P. This paper provides a theoretical foundation for AI-based verification and its impact on complexity theory, suggesting that sufficiently advanced AI systems could redefine computational verification.