Polynomial-time specialization of the instability checker to a fixed rational stability factor
ProvedStableMSR.Recovery.Supplement.fixed_checker_preprocessingGiven a polynomial-time machine for the uniform instability checker, one obtains a polynomial-time machine for a fixed rational stability factor. It accepts malformed or invalid specified inputs and on valid inputs prefixes the encoded stability factor before invoking the uniform checker on the original certificate. The checker acts on the pair consisting of the input string and the proposed certificate.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery.Supplement
theorem fixed_checker_preprocessing (b : Bool) (γ : ℚ) (hγ : 1 < γ)
(h : PvsNP.PolyTimeChecker (instabilityCheck b)) :
PvsNP.PolyTimeChecker (fun pair : Bits × Bits =>
match decodeSpecified pair.1 with
| none => true
| some S => if S.Valid then instabilityCheck b (packNats (ratNumbers γ) ++ pair.1,pair.2)
else true) := by sorry
end StableMSR.Recovery.Supplement
Source
Bit-model implementation step in Ravichandran and Reyzin, arXiv:2611.03547, Lemma C.3 and its application to Theorem 5.1(i), pp. 25–26. Encodings follow the mission's rational MSR language module.