Fixed-Degree Minkowski Factorization of Homogeneous Supports is NP-Complete

For integers k, N ≥ 1, let H_{k,N} = {x ∈ N^k : Σ_i x_i = N}. We study the following fixed-degree recognition problem: given an explicitly represented support S ⊆ H_{k,4}, decide whether S = Q + R, Q, R ⊆ H_{k,2}, where + denotes Minkowski addition of finite sets. We prove that this problem is NP-complete. The hardness persists on almost-complete instances: only O(k) of the Θ(k^4) states of H_{k,4} are missing, every missing state is square-free, and the corresponding missing-state 4-uniform hypergraph has maximum degree at most 8. The key structural result is an exact characterization for supports obtained by deleting square-free states from H_{k,4}. In this regime, quadratic factorization is equivalent to a binary edge-coloring CSP on the two-shadow of the missing hypergraph: missing four-sets force equal colors on opposite edges, whereas present four-cliques force at least one opposite pair to have different colors. A direct reduction from bounded-occurrence Monotone NAE-3-SAT then gives NP-hardness. We also formulate the result through a support invariant, factorization arity, and derive equivalent fixed-degree hardness statements for homogeneous formal polynomials over the Boolean semiring and for products of quadratic monomial ideals.