Theorem 1.3 — graph 3-colorability reduces to tensor -eigenvalue over
ProvedTensorNP.Eigen.theorem_1_3Graph 3-colorability is polynomial-time many-one reducible to tensor -eigenvalue over : there is a function , computable by a Turing machine in time polynomial in the length of its input, such that for every binary string ,
Here is the set of binary codes of simple graphs having a proper 3-coloring, and is the set of binary codes of rational tensors (any ) for which there is with
that is, for which is an eigenvalue with a real eigenvector (Problem 1.2 with , ).
Since graph 3-colorability is NP-complete (Karp 1972, cited by the paper and not formalized here), deciding tensor eigenvalue over is NP-hard.
Formalization Note "Polynomially reducible" is stated as Cook's polynomial-time many-one reducibility (CookPvsNP.PolyReducible): the paper's reduction maps one graph to one tensor, and a many-one reduction implies the oracle notion of the paper's §1.4. Instances are coded in binary as fixed in the definition file (rationals as numerator and denominator); the reduction produces integer tensors, which are rationals with denominator 1. NP-completeness of 3-colorability is not part of the statement.
import Mathlib import Definitions.Def_TensorNP_Eigen_Defs
namespace TensorNP.Eigen open CookPvsNP /-- Theorem 1.3: graph 3-colorability is polynomial-time many-one reducible to tensor `0`-eigenvalue over `ℝ` (Problem 1.2 with `F = ℝ`, `λ = 0`, rational tensors). -/ theorem theorem_1_3 : PolyReducible threeColLang tensorZeroEigLangR := by sorry end TensorNP.Eigen
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.