Documentation

MIPRE.Background.Tailored.Intro.CompleteContract

Completeness of the output tailored verifier, in the contract's form #

Phase 3c of planning/aldous-lyons-track.md (issue #281), the counterpart of Output.soundness_contract. For a λ-bounded tailored verifier T with a perfect ZPC strategy at index 2^n, whose normal form verifier T.ofTNFVT U0 is Cλ-bounded (C ≥ 2), the output tailored verifier at Cλ has a perfect ZPC strategy at index n as soon as its programs meet the specification IntroSpec.

The strategy is the honest strategy of the reference verifier's typed game (HonestChain.honest_zpc_ofTNFVT), which meets the three conditions of Complete.hasPerfectZPC_tpresented; Output.hasPerfectZPC_outTV carries it to the output. The input's answers fit the cutoff (2^n)^(Cλ) by the length bound of a λ-bounded verifier (Output.maxLen_le_of_isBounded).

Completeness of the output, in the contract's form: for a λ-bounded input T with a perfect ZPC strategy at index 2^n, whose normal form verifier is Cλ-bounded (C ≥ 2), when the output's programs meet the specification at Cλ, the output's n-th game has a perfect ZPC strategy.