P Versus NP in Probability: Limits, Closures, and Tail Exponents

We propose a resolution to a stochastic analogue of the P versus NP problem where algorithms are evaluated on ensembles of inputs and correctness is required only eventually almost surely. We define SP (Stochastic Polynomial-Time) as the class of distributional problems for which a polynomial-time algorithm exists with summable per-length error probabilities. Our main result establishes that SP is precisely the almost-sure closure of P lifted to distributional problems under an unweighted label-disagreement metric. Within NP-verifiable problems, the boundary between SP and its complement is determined by the summability of optimal error sequences, equivalently characterized by polynomial tail exponents above or below 1. Under standard cryptographic assumptions, we exhibit problems in NP with non-summable optimal error rates, yielding a clean separation in probability without claiming worst-case universality. We introduce a weighted-summability ladder that provides a testable, quantitative boundary and develop empirical protocols for tail-exponent estimation. This framework reframes a stochastic version of the P vs NP question in terms of eventual reliability on typical inputs, aligning theory with practical algorithmic requirements.