A polynomial-time canonical encoder for the graph-to-tensor construction
ProvedTensorNP.Eigen.colorTensor_canonical_encodercomplexity-theorytensorturing-machines
There exists a single total polynomial-time Cook-style Turing machine computing a function on arbitrary strings over the fixed four-symbol coding alphabet such that:
- If the input is the canonical binary adjacency-matrix code of a finite simple graph , then outputs the canonical rational tensor code of the explicitly constructed tensor .
- If the input is not the canonical code of any finite simple graph, then outputs the empty string.
This is the concrete parsing, validation, tensor emission, and polynomial-runtime obligation in the graph 3-colorability reduction. The empty fallback is a non-instance of the target language. The result concerns actual execution on the specified one-tape machine model; output-size estimates alone do not establish it.
Formalization Note. The finite graph and rational-tensor code formats, as well as the one-tape execution convention, are the platform’s explicit choices for realizing the construction of Hillar and Lim.
Preamble
import Definitions.Def_TensorNP_Eigen_Construction
Formal statement
namespace TensorNP.Eigen
open CookPvsNP ProjSchedTW.Complexity
/-- A total Cook-polynomial machine writes the precise tensor code of every
canonical graph input and the empty string on every non-graph input. -/
theorem colorTensor_canonical_encoder :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
(∀ (v : ℕ) (G : SimpleGraph (Fin v)), f (graphCode G) = tensorCode (colorTensor G)) ∧
(∀ w, (¬ ∃ (v : ℕ) (G : SimpleGraph (Fin v)), w = graphCode G) → f w = []) := by sorry
end TensorNP.Eigen
Source
Hillar and Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6), 2013, Definition 2.9 and proof of Theorem 1.3, https://arxiv.org/abs/0911.1393 ; source-specific machine realization for the platform encoding.