The class
DefinitionAvgPHETH_Supplement_PiPOaverage-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an oracle and , is the class of languages whose complement belongs to . Equivalently, iff for a verifier running in polynomial time with oracle and moves of polynomial length.
This is the class of the hard languages in the oracle barrier (Theorems 1.5 and 8.7).
Formalization Note is the published AvgPHETH.SigmaPO.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_SigmaPO
namespace AvgPHETH.Supplement
open AvgPHETH
/-- The class `Π_k^{p,O}`: languages whose complement is in `Σ_k^{p,O}`, i.e. languages with
`x ∈ L ⟺ ∀y₁ ∃y₂ ⋯ Q_k y_k V(x, y₁, …, y_k)` for a polynomial-time verifier `V` with oracle `O`
(Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), Theorem 1.5, p.4 (PDF 6); §8.1, p.38 (PDF 40)).
**Formalization Note** `Σ_k^{p,O}` is the published `AvgPHETH.SigmaPO`; a polynomial-time verifier
can be negated, so complementing the language is the same as starting the quantifiers with `∀`. -/
def PiPO (O : Set (List Bool)) (k : ℕ) : Set (Set (List Bool)) :=
{L | Lᶜ ∈ SigmaPO O k}
end AvgPHETH.Supplement
Source
Hirahara–Juvekar–Nanashima, Average-Case Hardness of PH from ETH-Type Hypotheses, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), Theorem 1.5, p.4 (PDF 6); §8.1, p.38 (PDF 40)