Theorem 3.7 — 3-colorability reduces to tensor bilinear feasibility over and over
ProvedTensorNP.Bilinear.theorem_3_7Let or . Graph 3-colorability is polynomial-time many-one reducible to tensor bilinear feasibility over (Problem 3.1): there is a function , computable by a Turing machine in time polynomial in the length of its input, such that for every binary word ,
where is the language of codes of rational tensors for which (9) has a solution with , , all nonzero. The statement asserts this for and for .
Since 3-colorability is NP-complete (Karp 1972), tensor bilinear feasibility is NP-hard over and over ; that consequence is cited by the paper and is not part of the formal statement.
Formalization Note The paper's §1.4 calls a problem polynomially reducible to another in the oracle (Cook) sense; the statement here is the stronger many-one (Karp) reducibility of the published definition CookPvsNP.PolyReducible, which is what the paper's proof constructs. Graphs and rational tensors are coded in binary as in TensorNP.Bilinear.Encoding. Polynomial-time computability refers to Cook's one-tape Turing machines. The reduction must map every word, including words that are not graph codes, and must handle the empty graph, for which the paper's tensor has no slices.
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_TensorNP_Bilinear_Encoding
namespace TensorNP.Bilinear
open CookPvsNP
/-- Theorem 3.7 (p. 0:17): graph 3-colorability is polynomial-time many-one reducible to tensor
bilinear feasibility (Problem 3.1), over `ℝ` and over `ℂ`. -/
theorem theorem_3_7 :
PolyReducible TensorNP.Eigen.threeColLang (tbfLang ℝ) ∧ PolyReducible TensorNP.Eigen.threeColLang (tbfLang ℂ) := by sorry
end TensorNP.Bilinear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.