Polynomial height of every moment-program word
ProvedLax263307Proofs.NativeMomentEncodingHeight.program_words_nativealgorithmscomputational-complexitygraph-theory
For a finite graph of order , target and moment level , every word in the actual rational encoding of its moment linear program satisfies
Here is the native moment-constructor size parameter. The bound includes coefficients, dimensions and all encoded metadata.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeNextInterfaces namespace Lax263307Proofs.NativeMomentEncodingHeight end Lax263307Proofs.NativeMomentEncodingHeight
Formal statement
theorem Lax263307Proofs.NativeMomentEncodingHeight.program_words_native : ∀ {n : Nat} (G : SimpleGraph (Fin n)) [inst : @DecidableRel (Fin n) (Fin n) (@SimpleGraph.Adj (Fin n) G)] (k r z : Nat),
@Membership.mem Nat (List Nat) (@List.instMembership Nat)
(@Lax109476.RationalEncoding.encodeProgram (Lax263307.MomentLP.rowCount n r) (Lax263307.MomentLP.dimension n r)
(@Lax263307.MomentLP.program n G inst k r))
z →
@LT.lt Nat instLTNat z
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(Lax263307Proofs.NativeMomentEncodingHeight.height n k r)) := by sorrySource