Theorem 1.2 (ii) — under
OpenAvgPHETH.Supplement.theorem_1_2_iiaverage-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be an oracle and . Suppose . Then every language can be solved by a deterministic algorithm with a oracle in time
where denotes the input length.
Each level of alternation available to the simulating algorithm saves one logarithmic factor in the exponent, measured in the input length. The case , without an oracle, is a result of Hirahara (2021). By Theorem 1.5 the bound cannot be improved by relativizing techniques.
Differences from the source:
- generalization: under , with no oracle, for every → every oracle and every , under , for every ; reason: the refinement on p.3 ("Theorem 1.2 (ii) only requires ") and the relativized proof on p.30; at , with such that , gives the hypothesis
- encoding: time → for one natural chosen after (published witnessTime); reason: only excludes , where the logarithm is ; the summand only matters for small
- encoding: deterministic algorithms with a oracle → the published DTimeOracle: one oracle language in SigmaPO O k, two-tape machines KarpLiptonOM.OracleTM; the oracle means no oracle; reason: the base mission's conventions; same classes up to polynomial overhead
Preamble
import Mathlib import Definitions.Def_AvgPHETH_DistSubAvgP import Definitions.Def_AvgPHETH_SigmaPO import Definitions.Def_AvgPHETH_DTimeOracle import Definitions.Def_AvgPHETH_witnessTime
Formal statement
namespace AvgPHETH.Supplement
open AvgPHETH
/-- **Theorem 1.2 (ii)** (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), p.3 (PDF 5)), in the refined relativized form of p.3 ("for
`L ∈ Σ_d^p`, … Theorem 1.2 (ii) only requires `DistΣ_{d+1}^p ⊆ AvgP`") and of its proof on p.30
(PDF 32): for every oracle `O` and all `d, k ≥ 0`, if `DistΣ_{d+1}^{p,O} ⊆ AvgP^O`, then every
`L ∈ Σ_d^{p,O}` is solved by a deterministic algorithm with a `Σ_k^{p,O}` oracle in time
`2^{O(n/log^{k+1} n)}`.
**Formalization Note** `2^{O(n/log^{k+1} n)}` is `⌈2^{c n/(log₂ max(n,2))^{k+1}}⌉ + c` (the published
`witnessTime c (k+1) id`) for a constant `c` chosen after `O, d, k, L`; the summand `c` is for small
`n`. -/
theorem theorem_1_2_ii (O : Set (List Bool)) (d k : ℕ) (L : Set (List Bool))
(hAvg : DistSubAvgP O (d + 1)) (hL : L ∈ SigmaPO O d) :
∃ c : ℕ, DTimeOracle (SigmaPO O k) (fun n => witnessTime c (k + 1) id n + c) L := by sorry
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.2 (ii), p.3 (PDF 5), with the refinement on p.3 and the proof on p.30 (PDF 32)