sgl_lautemann_bridge
Definitionbppcomplexity-theorycountingpolynomial-hierarchy
A sorry-free formal library for the amplified-verifier-to-Sigma₂ bridge: translation tuple encoding and decoding, exact shifted-cover semantics, polynomial witness bounds, the small- and large-cover arithmetic, eventual domination of polynomials by powers of two, finite-length exceptions, and the full Sigma₂ characterization conditional only on the long-input shifted-OR decider.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Definitions.Def_sgl_verifier_constructions
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Data.Nat.Basic
import Mathlib.Data.List.GetD
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Analysis.SpecificLimits.Normed
import Definitions.Def_sgl_finite_override_delegate
namespace SipserGacsLautemann
def coverShiftCount (randomBits : Nat) : Nat :=
randomBits + 1
def coverExistentialBits (randomBits : Nat) : Nat :=
coverShiftCount randomBits * randomBits
def decodeCoverTranslation (randomBits : Nat) (encoded : List Bool)
(i : Fin (coverShiftCount randomBits)) : List Bool :=
List.ofFn fun j : Fin randomBits =>
encoded.getD (i.val * randomBits + j.val) false
def coverVerifier (randomBits : Nat)
(verifier : List Bool → List Bool → Bool)
(input existential universal : List Bool) : Bool :=
decide (∃ i : Fin (coverShiftCount randomBits),
verifier input
(List.zipWith (· != ·) universal
(decodeCoverTranslation randomBits existential i)) = true)
def encodeCoverTranslations {randomBits : Nat}
(translations : Fin (coverShiftCount randomBits) → BitString randomBits) :
BitString (coverExistentialBits randomBits) :=
fun z =>
let ij := finProdFinEquiv.symm z
translations ij.1 ij.2
def unpackCoverTranslations {randomBits : Nat}
(encoded : BitString (coverExistentialBits randomBits)) :
Fin (coverShiftCount randomBits) → BitString randomBits :=
fun i j => encoded (finProdFinEquiv (i, j))
theorem encodeCoverTranslations_unpack {randomBits : Nat}
(encoded : BitString (coverExistentialBits randomBits)) :
encodeCoverTranslations (unpackCoverTranslations encoded) = encoded := by
funext z
change encoded (finProdFinEquiv (finProdFinEquiv.symm z)) = encoded z
rw [Equiv.apply_symm_apply]
theorem decodeCoverTranslation_encode {randomBits : Nat}
(translations : Fin (coverShiftCount randomBits) → BitString randomBits)
(i : Fin (coverShiftCount randomBits)) :
decodeCoverTranslation randomBits
(encodeCoverTranslations translations).toList i =
(translations i).toList := by
apply List.ext_get
· simp [decodeCoverTranslation, BitString.toList]
· intro n h₁ h₂
simp only [decodeCoverTranslation, BitString.toList, List.get_eq_getElem,
List.getElem_ofFn]
have hn : n < randomBits := by
simpa [BitString.toList] using h₂
have hindex :
i.val * randomBits + n <
coverExistentialBits randomBits := by
simp only [coverExistentialBits, coverShiftCount]
calc
i.val * randomBits + n <
i.val * randomBits + randomBits :=
Nat.add_lt_add_left hn _
_ = (i.val + 1) * randomBits := by
simp [Nat.add_mul]
_ ≤ (randomBits + 1) * randomBits :=
Nat.mul_le_mul_right randomBits (Nat.succ_le_iff.mpr i.isLt)
have hindex' :
i.val * randomBits + n <
(List.ofFn (encodeCoverTranslations translations)).length := by
simpa [BitString.toList] using hindex
rw [List.getD_eq_getElem _ _ hindex']
simp only [List.getElem_ofFn]
change
encodeCoverTranslations translations
⟨i.val * randomBits + n, hindex⟩ =
translations i ⟨n, hn⟩
have hflat :
(⟨i.val * randomBits + n, hindex⟩ :
Fin (coverExistentialBits randomBits)) =
finProdFinEquiv (i, ⟨n, hn⟩) := by
apply Fin.ext
simp [finProdFinEquiv, Nat.add_comm, Nat.mul_comm]
rw [hflat]
simp [encodeCoverTranslations]
theorem zipWith_xor_toList {n : Nat} (x y : BitString n) :
List.zipWith (· != ·) x.toList y.toList =
(xor x y).toList := by
apply List.ext_get
· simp [BitString.toList]
· intro i h₁ h₂
simp [BitString.toList, xor]
theorem coverVerifier_encode_iff {randomBits : Nat}
(verifier : List Bool → List Bool → Bool)
(input : List Bool)
(translations : Fin (coverShiftCount randomBits) → BitString randomBits)
(point : BitString randomBits) :
coverVerifier randomBits verifier input
(encodeCoverTranslations translations).toList point.toList = true ↔
∃ i : Fin (coverShiftCount randomBits),
verifier input (xor point (translations i)).toList = true := by
simp only [coverVerifier, decide_eq_true_eq]
apply exists_congr
intro i
rw [decodeCoverTranslation_encode, zipWith_xor_toList]
theorem coverVerifier_toList_iff {randomBits : Nat}
(verifier : List Bool → List Bool → Bool)
(input : List Bool)
(encoded : BitString (coverExistentialBits randomBits))
(point : BitString randomBits) :
coverVerifier randomBits verifier input
encoded.toList point.toList = true ↔
∃ i : Fin (coverShiftCount randomBits),
verifier input
(xor point (unpackCoverTranslations encoded i)).toList = true := by
simpa only [encodeCoverTranslations_unpack] using
(coverVerifier_encode_iff verifier input
(unpackCoverTranslations encoded) point)
theorem polynomiallyBounded_coverExistentialBits
{randomBits : Nat → Nat}
(hrandomBits : PolynomiallyBounded randomBits) :
PolynomiallyBounded
(fun n => coverExistentialBits (randomBits n)) := by
rcases hrandomBits with ⟨coefficient, degree, hbound⟩
refine
⟨(coefficient + 1) * (coefficient + 1), degree + degree, ?_⟩
intro n
let power := (n + 1) ^ degree
have hpower : 1 ≤ power := by
exact Nat.one_le_pow' degree n
have hr : randomBits n ≤ coefficient * power :=
hbound n
have hr' : randomBits n ≤ (coefficient + 1) * power :=
hr.trans (Nat.mul_le_mul_right power (Nat.le_succ coefficient))
have hrsucc : randomBits n + 1 ≤ (coefficient + 1) * power := by
calc
randomBits n + 1 ≤ coefficient * power + power :=
Nat.add_le_add hr hpower
_ = (coefficient + 1) * power := by
simp [Nat.add_mul]
calc
coverExistentialBits (randomBits n) =
(randomBits n + 1) * randomBits n := rfl
_ ≤ ((coefficient + 1) * power) *
((coefficient + 1) * power) :=
Nat.mul_le_mul hrsucc hr'
_ = ((coefficient + 1) * (coefficient + 1)) *
(n + 1) ^ (degree + degree) := by
simp only [power, pow_add]
ac_rfl
theorem card_bitString (n : Nat) :
Fintype.card (BitString n) = 2 ^ n := by
rw [Fintype.card_pi_const, Fintype.card_bool]
theorem acceptingCard_add_rejectingCard
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBits : Nat) :
acceptingCard verifier input randomBits +
rejectingCard verifier input randomBits =
Fintype.card (BitString randomBits) := by
classical
unfold acceptingCard rejectingCard
let p : BitString randomBits → Prop :=
fun random => verifier input random.toList = true
have hpartition :=
Finset.card_filter_add_card_filter_not
(s := (Finset.univ : Finset (BitString randomBits))) p
rw [show
(Finset.univ.filter fun random : BitString randomBits =>
verifier input random.toList = false) =
Finset.univ.filter fun random => ¬p random by
ext random
simp only [Finset.mem_filter, Finset.mem_univ, true_and, p]
cases verifier input random.toList <;> simp]
exact hpartition
theorem largeCoverArithmetic (inputLength randomBitCount bad : Nat)
(herror :
2 ^ (inputLength + 1) * bad ≤ 2 ^ randomBitCount) :
2 ^ randomBitCount * bad ^ (randomBitCount + 1) <
(2 ^ randomBitCount) ^ (randomBitCount + 1) := by
by_cases hbad : bad = 0
· subst bad
have hpositive :
0 < (2 ^ randomBitCount) ^ (randomBitCount + 1) :=
Nat.pow_pos (Nat.pow_pos (by decide : 0 < (2 : Nat)))
simpa using hpositive
have hbadPow : 0 < bad ^ (randomBitCount + 1) :=
Nat.pow_pos (Nat.pos_of_ne_zero hbad)
have hexponent :
randomBitCount <
(inputLength + 1) * (randomBitCount + 1) := by
calc
randomBitCount < randomBitCount + 1 :=
Nat.lt_succ_self randomBitCount
_ = 1 * (randomBitCount + 1) := by simp
_ ≤ (inputLength + 1) * (randomBitCount + 1) :=
Nat.mul_le_mul_right (randomBitCount + 1)
(Nat.succ_le_succ (Nat.zero_le inputLength))
have hpower :
2 ^ randomBitCount <
(2 ^ (inputLength + 1)) ^ (randomBitCount + 1) := by
rw [← pow_mul]
exact
(Nat.pow_lt_pow_iff_right (by decide : 1 < (2 : Nat))).2
hexponent
calc
2 ^ randomBitCount * bad ^ (randomBitCount + 1) <
(2 ^ (inputLength + 1)) ^ (randomBitCount + 1) *
bad ^ (randomBitCount + 1) :=
Nat.mul_lt_mul_of_pos_right hpower hbadPow
_ = (2 ^ (inputLength + 1) * bad) ^
(randomBitCount + 1) := by
rw [mul_pow]
_ ≤ (2 ^ randomBitCount) ^ (randomBitCount + 1) :=
Nat.pow_le_pow_left herror _
theorem smallCoverArithmetic (inputLength randomBitCount good : Nat)
(hshift : randomBitCount + 1 < 2 ^ (inputLength + 1))
(herror :
2 ^ (inputLength + 1) * good ≤ 2 ^ randomBitCount) :
(randomBitCount + 1) * good < 2 ^ randomBitCount := by
by_cases hgood : good = 0
· subst good
simpa using Nat.pow_pos (n := randomBitCount) (by decide : 0 < (2 : Nat))
exact
(Nat.mul_lt_mul_of_pos_right hshift (Nat.pos_of_ne_zero hgood)).trans_le
herror
theorem natPolynomial_lt_two_pow_eventually (coefficient degree : Nat) :
∃ threshold : Nat, ∀ n ≥ threshold,
coefficient * n ^ degree + 1 < 2 ^ n := by
have hlimit :
Filter.Tendsto
(fun n : Nat => (n : Real) ^ degree / (2 : Real) ^ n)
Filter.atTop (nhds 0) :=
tendsto_pow_const_div_const_pow_of_one_lt degree (by norm_num)
let epsilon : Real := 1 / (coefficient + 1)
have hepsilon : 0 < epsilon := by
dsimp [epsilon]
exact one_div_pos.mpr (by exact_mod_cast Nat.succ_pos coefficient)
have hratio :
∀ᶠ n : Nat in Filter.atTop,
(n : Real) ^ degree / (2 : Real) ^ n < epsilon :=
(tendsto_order.1 hlimit).2 epsilon hepsilon
have hone : ∀ᶠ n : Nat in Filter.atTop, 1 ≤ n :=
Filter.eventually_ge_atTop 1
rcases Filter.eventually_atTop.1 (hratio.and hone) with
⟨threshold, hthreshold⟩
refine ⟨threshold, ?_⟩
intro n hn
rcases hthreshold n hn with ⟨hratioN, hnOne⟩
have htwoPow : 0 < (2 : Real) ^ n :=
pow_pos (by norm_num) _
have hcoefficient : 0 < (coefficient + 1 : Real) := by
exact_mod_cast Nat.succ_pos coefficient
have hratioN' :
(n : Real) ^ degree <
epsilon * (2 : Real) ^ n :=
(div_lt_iff₀ htwoPow).mp hratioN
have hreal :
(coefficient + 1 : Real) * (n : Real) ^ degree <
(2 : Real) ^ n := by
calc
(coefficient + 1 : Real) * (n : Real) ^ degree <
(coefficient + 1 : Real) *
(epsilon * (2 : Real) ^ n) :=
mul_lt_mul_of_pos_left hratioN' hcoefficient
_ = (2 : Real) ^ n := by
simp [epsilon, hcoefficient.ne']
have hnat :
(coefficient + 1) * n ^ degree < 2 ^ n := by
exact_mod_cast hreal
have hnpower : 1 ≤ n ^ degree :=
Nat.one_le_pow degree n (Nat.zero_lt_of_lt hnOne)
exact
(calc
coefficient * n ^ degree + 1 ≤
coefficient * n ^ degree + n ^ degree :=
Nat.add_le_add_left hnpower _
_ = (coefficient + 1) * n ^ degree := by
simp [Nat.add_mul]).trans_lt hnat
theorem polynomiallyBounded_lt_two_pow_eventually
{randomBits : Nat → Nat}
(hrandomBits : PolynomiallyBounded randomBits) :
∃ threshold : Nat, ∀ n ≥ threshold,
randomBits n + 1 < 2 ^ (n + 1) := by
rcases hrandomBits with ⟨coefficient, degree, hbound⟩
rcases natPolynomial_lt_two_pow_eventually coefficient degree with
⟨threshold, hthreshold⟩
refine ⟨threshold, ?_⟩
intro n hn
have hpoly :
coefficient * (n + 1) ^ degree + 1 < 2 ^ (n + 1) :=
hthreshold (n + 1) (hn.trans (Nat.le_succ n))
exact (Nat.add_le_add_right (hbound n) 1).trans_lt hpoly
theorem PolynomiallyBounded.mono {f g : Nat → Nat}
(hf : PolynomiallyBounded f) (hgf : ∀ n, g n ≤ f n) :
PolynomiallyBounded g := by
rcases hf with ⟨coefficient, degree, hbound⟩
exact
⟨coefficient, degree, fun n => (hgf n).trans (hbound n)⟩
def lautemannExistentialBits (threshold : Nat)
(randomBits : Nat → Nat) (n : Nat) : Nat :=
if n < threshold then 0
else coverExistentialBits (randomBits n)
def lautemannUniversalBits (threshold : Nat)
(randomBits : Nat → Nat) (n : Nat) : Nat :=
if n < threshold then 0
else randomBits n
noncomputable def lautemannVerifier (language : Language)
(threshold : Nat) (randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(input existential universal : List Bool) : Bool := by
classical
exact if input.length < threshold then
decide (input ∈ language)
else
coverVerifier universal.length verifier
input existential universal
theorem polynomiallyBounded_lautemannExistentialBits
(threshold : Nat) {randomBits : Nat → Nat}
(hrandomBits : PolynomiallyBounded randomBits) :
PolynomiallyBounded
(lautemannExistentialBits threshold randomBits) := by
apply
(polynomiallyBounded_coverExistentialBits hrandomBits).mono
intro n
simp only [lautemannExistentialBits]
split <;> simp
theorem polynomiallyBounded_lautemannUniversalBits
(threshold : Nat) {randomBits : Nat → Nat}
(hrandomBits : PolynomiallyBounded randomBits) :
PolynomiallyBounded
(lautemannUniversalBits threshold randomBits) := by
apply hrandomBits.mono
intro n
simp only [lautemannUniversalBits]
split <;> simp
theorem setCard_acceptingSet
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBits : Nat) :
setCard
(fun random : BitString randomBits =>
verifier input random.toList = true) =
acceptingCard verifier input randomBits := by
rfl
theorem card_sub_acceptingSet_eq_rejectingCard
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBits : Nat) :
Fintype.card (BitString randomBits) -
setCard
(fun random : BitString randomBits =>
verifier input random.toList = true) =
rejectingCard verifier input randomBits := by
rw [setCard_acceptingSet]
have hsum :=
acceptingCard_add_rejectingCard verifier input randomBits
omega
theorem lautemann_characterization
(language : Language)
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(herror :
∀ input : List Bool,
(input ∈ language →
2 ^ (input.length + 1) *
rejectingCard verifier input (randomBits input.length) ≤
Fintype.card (BitString (randomBits input.length))) ∧
(input ∉ language →
2 ^ (input.length + 1) *
acceptingCard verifier input (randomBits input.length) ≤
Fintype.card (BitString (randomBits input.length))))
(smallCoverObstruction :
∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
shifts * setCard set < Fintype.card (BitString n) →
∀ translations : Fin shifts → BitString n,
¬ shiftedCover set translations)
(largeCoverExistence :
∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
Fintype.card (BitString n) *
(Fintype.card (BitString n) - setCard set) ^ shifts <
(Fintype.card (BitString n)) ^ shifts →
∃ translations : Fin shifts → BitString n,
shiftedCover set translations)
(threshold : Nat)
(hthreshold : ∀ n ≥ threshold,
randomBits n + 1 < 2 ^ (n + 1)) :
∀ input : List Bool,
input ∈ language ↔
∃ existential :
BitString
(lautemannExistentialBits threshold randomBits input.length),
∀ universal :
BitString
(lautemannUniversalBits threshold randomBits input.length),
lautemannVerifier language threshold randomBits verifier
input existential.toList universal.toList = true := by
classical
intro input
by_cases hshort : input.length < threshold
· simp [lautemannExistentialBits, lautemannUniversalBits,
lautemannVerifier, hshort]
rw [show
lautemannExistentialBits threshold randomBits input.length =
coverExistentialBits (randomBits input.length) by
simp [lautemannExistentialBits, hshort]]
rw [show
lautemannUniversalBits threshold randomBits input.length =
randomBits input.length by
simp [lautemannUniversalBits, hshort]]
simp only [lautemannVerifier]
simp only [if_neg hshort]
let r := randomBits input.length
let acceptingSet : BitString r → Prop :=
fun random => verifier input random.toList = true
constructor
· intro hmember
have hreject :=
(herror input).1 hmember
have hlarge :
Fintype.card (BitString r) *
(Fintype.card (BitString r) -
setCard acceptingSet) ^ coverShiftCount r <
(Fintype.card (BitString r)) ^ coverShiftCount r := by
rw [card_sub_acceptingSet_eq_rejectingCard,
card_bitString]
exact largeCoverArithmetic input.length r _
(by simpa [r, card_bitString] using hreject)
obtain ⟨translations, hcover⟩ :=
largeCoverExistence acceptingSet hlarge
refine ⟨encodeCoverTranslations translations, ?_⟩
intro point
have hpointLength : point.toList.length = r := by
simp [BitString.toList, r]
rw [hpointLength]
rw [coverVerifier_encode_iff]
exact hcover point
· rintro ⟨encoded, hall⟩
by_contra hnonmember
have haccept :=
(herror input).2 hnonmember
have hsmall :
coverShiftCount r * setCard acceptingSet <
Fintype.card (BitString r) := by
rw [setCard_acceptingSet, card_bitString]
exact smallCoverArithmetic input.length r _
(by
exact hthreshold input.length (Nat.le_of_not_gt hshort))
(by simpa [r, card_bitString] using haccept)
have hnotCover :=
smallCoverObstruction acceptingSet hsmall
(unpackCoverTranslations encoded)
apply hnotCover
intro point
have hallPoint := hall point
have hpointLength : point.toList.length = r := by
simp [BitString.toList, r]
rw [hpointLength] at hallPoint
rw [coverVerifier_toList_iff] at hallPoint
exact hallPoint
theorem amplified_verifier_implies_sigma_two_of_cover_lemmas_of_dpt
(language : Language)
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(hrandomBits : PolynomiallyBounded randomBits)
(herror :
∀ input : List Bool,
(input ∈ language →
2 ^ (input.length + 1) *
rejectingCard verifier input (randomBits input.length) ≤
Fintype.card (BitString (randomBits input.length))) ∧
(input ∉ language →
2 ^ (input.length + 1) *
acceptingCard verifier input (randomBits input.length) ≤
Fintype.card (BitString (randomBits input.length))))
(smallCoverObstruction :
∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
shifts * setCard set < Fintype.card (BitString n) →
∀ translations : Fin shifts → BitString n,
¬ shiftedCover set translations)
(largeCoverExistence :
∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
Fintype.card (BitString n) *
(Fintype.card (BitString n) - setCard set) ^ shifts <
(Fintype.card (BitString n)) ^ shifts →
∃ translations : Fin shifts → BitString n,
shiftedCover set translations)
(threshold : Nat)
(hthreshold :
∀ n ≥ threshold,
randomBits n + 1 < 2 ^ (n + 1))
(hlautemannVerifier :
DecidesInPolynomialTime
(fun input : Fin 3 → List Bool =>
lautemannVerifier language threshold randomBits verifier
(input 0) (input 1) (input 2) = true)) :
InSigmaTwoP language := by
refine
⟨lautemannExistentialBits threshold randomBits,
lautemannUniversalBits threshold randomBits,
lautemannVerifier language threshold randomBits verifier,
polynomiallyBounded_lautemannExistentialBits
threshold hrandomBits,
polynomiallyBounded_lautemannUniversalBits
threshold hrandomBits,
hlautemannVerifier, ?_⟩
exact
lautemann_characterization
language randomBits verifier herror
smallCoverObstruction largeCoverExistence
threshold hthreshold
theorem lautemannVerifier_dpt_of_coverVerifier_dpt
(language : Language)
(threshold : Nat)
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(hcover :
DecidesInPolynomialTime
(fun input : Fin 3 → List Bool =>
coverVerifier (input 2).length verifier
(input 0) (input 1) (input 2) = true)) :
DecidesInPolynomialTime
(fun input : Fin 3 → List Bool =>
lautemannVerifier language threshold randomBits verifier
(input 0) (input 1) (input 2) = true) := by
classical
have hoverride :=
decidesInPolynomialTime_finiteOverride
(tapes := 2) language threshold
(fun input : Fin 3 → List Bool =>
coverVerifier (input 2).length verifier
(input 0) (input 1) (input 2) = true)
hcover
apply hoverride.congr
intro input
have hfirst :
firstTapeIndex 2 = (0 : Fin 3) := by rfl
rw [hfirst]
by_cases hshort : (input 0).length < threshold
· simp [hshort, lautemannVerifier]
· simp [hshort, lautemannVerifier]
end SipserGacsLautemannSource
The shifted-cover argument in the Sipser–Gács–Lautemann theorem, including the standard finite-exception cleanup.