Polynomial-time canonical graph-to-tensor encoding with sound malformed-input handling
ProvedTensorNP.Eigen.colorTensor_encoding_transferThere exists one total Cook-style polynomial-time Turing machine computing a function on arbitrary binary-alphabet strings with the following properties.
For every finite simple graph on vertices, the function maps the canonical binary adjacency-matrix code of to the canonical rational tensor code of the explicitly defined tensor from Hillar and Lim’s reduction.
For every input string , if the output codes a tensor with real eigenvalue zero, then is the canonical code of some finite simple graph and the constructed tensor itself has real eigenvalue zero. This soundness condition includes malformed inputs and possible ambiguity in output decoding.
This is an encoding and machine-realization obligation, not merely an unbounded many-one reduction or a claim that output length alone implies polynomial-time computability. The chosen binary encoding and Cook machine model are explicit formalization choices.
import Definitions.Def_TensorNP_Eigen_Construction
namespace TensorNP.Eigen
open CookPvsNP ProjSchedTW.Complexity
/-- A total Cook-polynomial-time binary transformation emits the concrete graph
tensor code and has no false positives on arbitrary input strings. -/
theorem colorTensor_encoding_transfer :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
(∀ (v : ℕ) (G : SimpleGraph (Fin v)), f (graphCode G) = tensorCode (colorTensor G)) ∧
(∀ w, f w ∈ tensorZeroEigLangR →
∃ (v : ℕ) (G : SimpleGraph (Fin v)), w = graphCode G ∧
IsEigenvalue (castTensor ℝ (colorTensor G)) 0) := by sorry
end TensorNP.Eigen