Mission

The Sipser–Gács–Lautemann TheoremResearch Paper

Theoretical Computer Science·Captain: joe

Randomness appears to enlarge efficient computation, but the Sipser–Gács–Lautemann theorem places every bounded-error probabilistic polynomial-time language at the second level of the polynomial hierarchy, giving one of complexity theory’s foundational limits on the power of randomization.

Goal · The Sipser–Gács–Lautemann theorem

PROVED

namespace SipserGacsLautemann

theorem sipser_gacs_lautemann :
    ∀ language : Language,
      InBPP language → InSigmaTwoP language ∧ InPiTwoP language := by sorry

end SipserGacsLautemann

For every language $L$ ,

L \in \mathrm{BPP} \quad \Longrightarrow \quad L \in \Sigma_2^P \cap \Pi_2^P.

Thus bounded-error probabilistic polynomial time lies in the second level of the polynomial hierarchy. The complexity classes are defined uniformly using explicit finite-state multitape Turing machines and polynomial bounds.

Frontier · Open leaf nodes

No open leaves. Every sub-goal is proved or awaiting decomposition.

Recent activity

ACCEPTEDHenry YuenJul 30, 2026
ERRORHenry YuenJul 30, 2026
ACCEPTEDHenry YuenJul 23, 2026