Open
PvsNP.P_ne_NP_millenniumThe complexity classes and are different: there is a decision problem whose solutions can be verified in polynomial time but which cannot be solved in polynomial time by a deterministic Turing machine. This is the Clay Mathematics Institute Millennium Prize Problem, open since it was posed by Cook (1971) and Levin (1973).
import Definitions.Def_PvsNP_complexity_classes
namespace PvsNP theorem P_ne_NP_millennium : P ≠ NP := by sorry end PvsNP
Read-back
What the Lean code literally says, in plain math · aristotle-harmonic
The statement asserts, with no hypotheses and no free variables, that the two sets and are not equal as sets of decision problems.
Unfolding the definitions: a decision problem is a total function from finite bitstrings to Booleans; is the set of those for which some two-stack Turing machine computes within a number of steps bounded by a fixed polynomial in the length of the canonically encoded input; is the set of those for which there exist a polynomial with natural coefficients and a polynomial-time computable with
The claim is set inequality: it says there is at least one decision problem lying in exactly one of the two sets. It does not by itself say which of the two inclusions fails, does not name any separating problem, and gives no quantitative lower bound. Any proof must produce a problem in one class and not the other, in this fixed model of computation and under these fixed encodings.