Uniform polynomial-time binary kernel search with a nonzero prefix
OpenMetricSelfDualCompletion.Completion.AGProof.KernelSearch.uniform_nonzero_prefix_kernel_searchcoding-theorycomplexity-theorycomputabilitylinear-algebra
There exists one deterministic polynomial-time TM2 function on finite bit strings which, for every rectangular binary matrix A and prefix length q encoded with the original encMatrix and unary encNat, returns true followed by the original encoding of a kernel vector with a nonzero coordinate among the first min(q,c) coordinates whenever one exists, and returns the empty string otherwise. Its running time is polynomial on every input string, including malformed inputs. This is an auxiliary algorithmic primitive for the AG key-equation step in STOC 2027 submission #5; it does not assert an AG basis constructor or completion of Theorem11.
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_MetricSelfDualCompletion_Completion_Encoding open Matrix MetricSelfDualCompletion.Completion
Formal statement
theorem MetricSelfDualCompletion.Completion.AGProof.KernelSearch.uniform_nonzero_prefix_kernel_search :
∃ f : List Bool → List Bool,PvsNP.PolyTimeComputable f∧
∀(r c:ℕ)(A:Matrix (Fin r) (Fin c) (ZMod 2))(q:ℕ),
((∃ x : Fin c → (ZMod 2),A*ᵥx=0∧∃ j : Fin c,j.val<q∧x j≠0) →
∃ x : Fin c → (ZMod 2),A*ᵥx=0∧(∃ j : Fin c,j.val<q∧x j≠0)∧
f (encMatrix A++encNat q)=true::encVec x) ∧
((¬∃ x : Fin c → (ZMod 2),A*ᵥx=0∧∃ j : Fin c,j.val<q∧x j≠0) →
f (encMatrix A++encNat q)=[]) := by sorry
Source
Auxiliary constructive linear-algebra primitive for STOC2027 submission #5, Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance, Theorem11 algorithmic component. Uses exact published MetricSelfDualCompletion encMatrix/encVec/encNat and PvsNP.PolyTimeComputable machine semantics, with the accepted tree-stack to TM2 compiler.