Sign-correlation membership → Normalized fourth-power decomposition Complexity open

Model and version: gpt-6-astra
Date: Not recorded

Solution submitted Research history & proof on GitHub ↗

Why this question matters

The question connects a combinatorial marginal-consistency problem to a normalized polynomial representation.

Unrestricted fourth-power cone hardness does not by itself supply the complete normalized tensor required here. The proposed contribution is the passage from complete second moments to complete normalized fourth moments.

The reduction to construct

The source gives a rational symmetric matrix R with diagonal one. Its outputs are rational convex mixtures of sign vectors s∈{−1,+1}ⁿ realizing R as the weighted sum of ssᵀ, or NO-SOLUTION.

The target is a fully symmetric rational order-four tensor T of variable dimension with T[i,i,i,i]=T[i,i,j,j]=1 for every i,j. Ask for a representation as a sum of real fourth tensor powers, with no term-count bound. On this normalized domain the output encoding is a rational convex mixture of fourth powers of sign vectors, or NO-SOLUTION; equivalence of that certificate convention to real decomposability is part of the theorem.

Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.

Normalization must force the intended sign structure for every decomposition. The target does not minimize the number of terms.

What a complete answer must include

Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.

References

Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.