Project a native blow-up answer to its original membership mask
ProvedLax263307Proofs.NativeWeightedOutput.command_spec_nativealgorithmscomputational-complexitygraph-theory
Let be natural copy counts on vertices, let , and let be any subset of the numbered copies. Assume and , a stored owner table, the mask of , and the stated output-buffer lengths. The fixed command appends precisely the original-vertex membership encoding of the projection of :
It uses at most instructions. This output contract applies to every subset of copies, independently of any later independence or approximation argument.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativePhaseInterfaces namespace Lax263307Proofs.NativeWeightedOutput end Lax263307Proofs.NativeWeightedOutput
Formal statement
theorem Lax263307Proofs.NativeWeightedOutput.command_spec_native : ∀ {n : Nat} (B : Nat) (copies : Fin n → Nat) (I : Finset (Fin (∑ v : Fin n, copies v))),
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) n (∑ v : Fin n, copies v))
(@OfNat.ofNat Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
B →
@LT.lt Nat instLTNat
(@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))) (∑ v : Fin n, copies v))
B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (σ.vars "input.n") n)
(And (@Eq Nat (σ.vars "blowup.length") (∑ v : Fin n, copies v))
(And (@Eq Nat (σ.vars "root.mask") (@Lax263307Proofs.NativeMasks.mask (∑ v : Fin n, copies v) I))
(And
(Lax455465Proofs.RamVirtualState.Prefix (@Lax263307Proofs.NativeBlowUp.owners n copies) "blowup.owner"
σ)
(And (@LE.le Nat instLENat (∑ v : Fin n, copies v) (@List.length Nat (σ.arrs "image.labels")))
(@Eq Nat (@List.length Nat (σ.arrs "image.output")) n))))))
Lax263307Proofs.NativeWeightedOutput.command
(fun (σ τ : Lax808846Proofs.Imp.Env) =>
@Eq (List Nat) τ.out
(@HAppend.hAppend (List Nat) (List Nat) (List Nat) (@instHAppendOfAppend (List Nat) (@List.instAppend Nat))
σ.out
(@Lax263307.IndependentSetEncoding.encodeOutput n
(@Lax263307.IndependentBlowUp.project n copies
(@Finset.image (Fin (∑ v : Fin n, copies v)) (@Lax263307.IndependentBlowUp.Vertex n copies)
(fun (a b : @Lax263307.IndependentBlowUp.Vertex n copies) =>
@Sigma.instDecidableEqSigma (Fin n) (fun (v : Fin n) => Fin (copies v)) (instDecidableEqFin n)
(fun (a : Fin n) => instDecidableEqFin (copies a)) a b)
(@DFunLike.coe (Equiv (Fin (∑ v : Fin n, copies v)) (@Lax263307.IndependentBlowUp.Vertex n copies))
(Fin (∑ v : Fin n, copies v))
(fun (x : Fin (∑ v : Fin n, copies v)) => @Lax263307.IndependentBlowUp.Vertex n copies)
(@EquivLike.toFunLike
(Equiv (Fin (∑ v : Fin n, copies v)) (@Lax263307.IndependentBlowUp.Vertex n copies))
(Fin (∑ v : Fin n, copies v)) (@Lax263307.IndependentBlowUp.Vertex n copies)
(@Equiv.instEquivLike (Fin (∑ v : Fin n, copies v))
(@Lax263307.IndependentBlowUp.Vertex n copies)))
(@Lax263307.WeightedAlgorithm.labeling n copies))
I)))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 24) (instOfNatNat (nat_lit 24))) n)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 44) (instOfNatNat (nat_lit 44))) (∑ v : Fin n, copies v)))
(@OfNat.ofNat Nat (nat_lit 36) (instOfNatNat (nat_lit 36)))) := by sorrySource