Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time canonical graph-to-tensor encoding with sound malformed-input handling

Proved
TensorNP.Eigen.colorTensor_encoding_transfer

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

complexity-theorytensorturing-machines

There 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 GGG on vvv vertices, the function maps the canonical binary adjacency-matrix code of GGG to the canonical rational tensor code of the explicitly defined tensor TGT_GTG​ from Hillar and Lim’s reduction.

For every input string www, if the output codes a tensor with real eigenvalue zero, then www is the canonical code of some finite simple graph GGG and the constructed tensor TGT_GTG​ 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.

Preamble
import Definitions.Def_TensorNP_Eigen_Construction
Formal statement
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
Source
Hillar and Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6), 2013, Definition 2.9, Lemmas 2.7–2.10, and proof of Theorem 1.3; https://arxiv.org/abs/0911.1393 ; binary-code and machine realization obligation 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