Lemma C.3 — polynomial rational instability witnesses
ProvedStableMSR.Recovery.Supplement.rational_instability_witnessFor rational finite metric inputs and rational , under either perturbation convention a specified feasible exact- partition is unstable exactly when it has a rational perturbation and a distinct feasible competitor of no greater perturbed cost, encoded by a polynomial-length certificate.
For a binary input encoding , the metric table and the specified partition, there are absolute natural constants such that
For each convention , the explicit checker runs in polynomial time in . It tests the decoded rational perturbation bounds, symmetry, competitor feasibility and distinctness, the cost inequality, and the triangle inequalities when needed. This includes and supplies the certificate ingredient for coNP membership.
Differences from the source:
- encoding: Finite ordered metric input and unordered exact-k partitions → Fin n points, real metric arrays, and finite sets of nonempty disjoint blocks; reason: Input-order relabelling preserves every source instance and partition; base published definitions are reused without extra conditions
- encoding: Rational input and rational gamma >= 1; polynomial binary-length perturbation and competitor → The rational factor is a leading binary input field; a uniform positive prefactor and natural exponent bound the concrete certificate length; reason: The input length includes the factor as well as the rational table and labels; both perturbation conventions use the same literal certificate format
- encoding: Can be verified in polynomial time → PvsNP.PolyTimeChecker for the concrete decoded perturbation-and-competitor checking relation; reason: This is the standard multi-stack Turing machine notion; no polynomial-time verification assumption is added
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery.Supplement
theorem rational_instability_witness :
∃ a b : ℕ, 0 < a ∧
∀ metric : Bool, PvsNP.PolyTimeChecker (instabilityCheck metric) ∧
∀ w γ S, decodeInstabilityInput w = some (γ,S) → 1 ≤ γ → S.Valid →
(¬ ConventionStable metric S.input.dist S.input.k γ S.partition ↔
∃ y : Bits, y.length ≤ a * (w.length + 1) ^ b ∧
instabilityCheck metric (w,y) = true) := by sorry
end StableMSR.Recovery.Supplement