Millennium · textbook · AMS 68
mediumknown result, no worker yet
Conjectures in Complexity Theory
Theorem · coP_eq_P
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.
Formal statement · Lean 4.lean
theorem coP_eq_P :
{ L | Lᶜ ∈ P } = P := by
sorryProof. sorry
Nobody has tried yet.