A compiled polynomial-time program for valid flow-cut instances
ProvedLax455465Proofs.RamValidCompilation.exists_programalgorithmscomputational-complexitygraph-theory
There are one fixed RAM program and polynomial width and time bounds . Every valid rational product-demand instance with at least two positive-demand vertices has one certificate such that
and returns its encoding in at most steps at every host width at least . Undirected inputs carry the symmetry promise.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax455465Proofs.RamValidCompilation.exists_program : ∃ (p : Lax808846.Ram.Program) (WB : Polynomial ℕ) (TB : Polynomial ℕ),
∀ {n : ℕ} (kind : Lax455465.ProductNetwork.EdgeKind) (I : Lax455465.RationalEncoding.RationalInstance n),
(kind = Lax455465.ProductNetwork.EdgeKind.undirected → I.network.IsUndirected) →
2 ≤ Lax455465.ProductNetwork.supportCount I.weights →
∃ (certificate : Lax455465.FlowCutCertificate.Certificate n),
Lax455465.FlowCutCertificate.IsValid kind I 512 certificate ∧
∀ (W : ℕ),
Polynomial.eval (Lax759944.BinaryWordEncoding.bitSize (Lax455465.RationalEncoding.encodeInput kind I))
WB ≤
W →
∃
t ≤
Polynomial.eval
(Lax759944.BinaryWordEncoding.bitSize (Lax455465.RationalEncoding.encodeInput kind I)) TB,
Lax808846.Ram.RunsTo W p
((Lax455465.RationalEncoding.encodeInput kind I).length ::
Lax455465.RationalEncoding.encodeInput kind I)
(Lax455465.FlowCutCertificate.encodeCertificate certificate) t := by sorrySource