3-SAT → Total-budget Hadamard complexity Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
This targets the total rank cost used to measure Hadamard representation size, rather than a preassigned allocation of ranks.
Hardness under separate factor-rank bounds does not establish hardness under their sum. Every allocation within the total budget belongs to this question.
The reduction to construct
A source instance is an explicitly encoded Boolean formula with at most three literals per clause. Its outputs are satisfying Boolean assignments, or NO-SOLUTION when the formula is unsatisfiable.
Given a nonempty rational matrix M and nonnegative integer budget b, find real A,B with M=A⊙B and rank(A)+rank(B)≤b, or report NO-SOLUTION. Witnesses encode both rank factorizations over one real algebraic primitive element; zero widths and either factor order are allowed.
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.
Soundness must exclude every allocation within the sum budget. Hardness for a single pair of widths cannot establish this theorem.
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-15. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.