Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A polynomial-time canonical encoder for the graph-to-tensor construction

Proved
TensorNP.Eigen.colorTensor_canonical_encoder

by kmehltretter82 · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorytensorturing-machines

There exists a single total polynomial-time Cook-style Turing machine computing a function fff 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 GGG, then fff outputs the canonical rational tensor code of the explicitly constructed tensor TGT_GTG​.
  • If the input is not the canonical code of any finite simple graph, then fff 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me