Theorem 6.2 — 3-colorability reduces to deciding whether is an - or -singular value
ProvedTensorNP.Bilinear.theorem_6_2Let or and . Graph 3-colorability is polynomial-time many-one reducible to the problem of deciding, for a rational tensor , whether is an -singular value of over (Definition 6.1):
for each of the four choices of .
By the NP-completeness of 3-colorability (cited, not formalized), deciding whether is an - or -singular value of a tensor is NP-hard over and over , which is the paper's statement.
Formalization Note "NP-hard" is rendered as a polynomial-time many-one reduction from 3-colorability, the reduction the paper's argument gives ("immediate from Theorem 3.7"). "( or )" is read as the claim for each of the two notions. Codes and polynomial-time computability are as in Theorem 3.7.
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_TensorNP_Bilinear_Encoding import Definitions.Def_TensorNP_Bilinear_SingularValue
namespace TensorNP.Bilinear
open CookPvsNP
/-- Theorem 6.2 (p. 0:22): graph 3-colorability is polynomial-time many-one reducible to deciding
whether `σ = 0` is an ℓ²-singular value, and to deciding whether `σ = 0` is an ℓ³-singular
value, of a rational tensor, over `ℝ` and over `ℂ`. -/
theorem theorem_6_2 :
PolyReducible TensorNP.Eigen.threeColLang (zeroL2SingLang ℝ) ∧ PolyReducible TensorNP.Eigen.threeColLang (zeroL2SingLang ℂ) ∧
PolyReducible TensorNP.Eigen.threeColLang (zeroL3SingLang ℝ) ∧
PolyReducible TensorNP.Eigen.threeColLang (zeroL3SingLang ℂ) := by sorry
end TensorNP.Bilinear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.