Polynomial native serialization of a cut and converted primal flow
OpenLax455465Proofs.RamOutputResources.command_specalgorithmscomputational-complexitygraph-theory
Fix a rational network instance , a cut , and a componentwise nonnegative primal vector whose height is bounded by . Under the stated polynomial word budget and initialized conversion/output buffers, the fixed writer returns exactly the joint encoding of and the converted primal flow:
This is a reusable source interface for composing the complete finite-program implementation.
Retired because the namespace-wrapped declaration compiled during publication but the proof-comparison parser rejects that header (expected token / unknown full theorem identifier). The mathematically identical, fully qualified declaration is Lax455465Proofs.RamOutputResources.command_spec_native.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeDetailedInterfaces
Formal statement
namespace Lax455465Proofs.RamOutputResources
theorem command_spec : ∀ (P : @Polynomial Nat Nat.instSemiring) {n : Nat} (kind : Lax455465.ProductNetwork.EdgeKind)
(I : Lax455465.RationalEncoding.RationalInstance n) (S : Finset (Fin n))
(z :
Fin
(Nat.add ((1:Nat))
(Nat.mul (Nat.mul n n)
(Nat.mul n n))) →
Rat)
(hz :
∀
(i :
Fin
(Nat.add ((1:Nat))
(Nat.mul (Nat.mul n n)
(Nat.mul n n)))),
@LE.le Rat Rat.instLE (@OfNat.ofNat Rat (nat_lit 0) (@Rat.instOfNat (nat_lit 0))) (z i)),
(∀
(i :
Fin
(Nat.add ((1:Nat))
(Nat.mul (Nat.mul n n)
(Nat.mul n n)))),
Lax455465Proofs.LpInputSize.Height
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
((2:Nat))
(@Polynomial.eval Nat Nat.instSemiring
(Lax759944.BinaryWordEncoding.bitSize (@Lax455465.RationalEncoding.encodeInput n kind I)) P))
(z i)) →
∀ (W : Nat),
Nat.le
(@Polynomial.eval Nat Nat.instSemiring
(Lax759944.BinaryWordEncoding.bitSize (@Lax455465.RationalEncoding.encodeInput n kind I))
(Lax455465Proofs.RamOutputResources.wordBound P))
W →
Lax808846Proofs.Reasoning.Spec
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
((2:Nat)) W)
(fun (σ : Lax808846Proofs.Imp.Env) =>
And
(Lax455465Proofs.RamFlowConvert.Context kind
(@Lax455465Proofs.RamOptimalDecode.vector
(Nat.add
((1:Nat))
(Nat.mul
(Nat.mul n n)
(Nat.mul n n)))
z hz)
σ)
(And (@Eq Nat (σ.vars "metric.n") n)
(And
(Lax455465Proofs.RamVirtualState.Prefix
(Lax455465Proofs.RamUnsignedBuffer.encode (@Lax455465Proofs.CutScoreData.vertexFlags n S))
"cut.flags" σ)
(And
(Nat.lt
(Nat.mul
((2:Nat))
(Nat.add
((1:Nat))
(Nat.mul
(Nat.mul n n)
(Nat.mul n n))))
(@List.length Nat (σ.arrs "flow.converted")))
(@Eq (List Nat) σ.out (@List.nil Nat))))))
Lax455465Proofs.RamJointOutput.command
(fun (x τ : Lax808846Proofs.Imp.Env) =>
@Eq (List Nat) τ.out
(@Lax455465.FlowCutCertificate.encodeCertificate n
(@Lax455465.FlowCutCertificate.Certificate.mk n S
(@Lax455465Proofs.CertificatePostprocessing.convertFlow n kind
(@Lax455465Proofs.CertificatePostprocessing.primalFlow n z)))))
(@Polynomial.eval Nat Nat.instSemiring
(Lax759944.BinaryWordEncoding.bitSize (@Lax455465.RationalEncoding.encodeInput n kind I))
(Lax455465Proofs.RamOutputResources.timeBound P)) := by sorry
end Lax455465Proofs.RamOutputResources
Source