All open problems
Source labels openChecked July 26, 2026
Millennium ProblemsComputer science
Conjectures in Complexity Theory
P ≠ NP*:
Mathematical statement
P ≠ NP*:
The conjecture that the complexity classes P and NP are not equal.
Statement source: Millennium Problems statement material
Statement terms: Source-specific
Source-specific terms. Therefore does not assert reuse rights beyond attributed display.
Statement artifacts, not proofs
These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.
Pinned Lean formulation 1
P_ne_NP
Complete statement target, proof intentionally absentLean 4
theorem P_ne_NP : P ≠ NP := by sorry /--**NP ≠ coNP**: The conjecture that the complexity classes NP and coNP are not equal.-/@[category research open, AMS 68]theorem NP_ne_coNP : NP ≠ coNP := by sorry /--The theorem that the set of complements of languages in P is itself P. This can be proven by observing that the boolean negation function is computable in polynomial time,and that compositions of poly-time computable functions are also poly-time computable.-/@[category textbook, AMS 68]theorem coP_eq_P : { L | Lᶜ ∈ P } = P := by sorry- Statement source
- Formal Conjectures
- Lean version
- v4.27.0
- Placeholder
- Present; no proof artifact
- Source evidence
- Pinned source index
- Fidelity review
- Community formulation
References