3-SAT → Exact Hadamard decomposition Complexity open

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

Solution submitted Research history & proof on GitHub ↗

Why this question matters

Hadamard factorization is a compact matrix representation; this asks whether deciding exact representability is computationally hard.

The cited Hadamard decomposition work motivates the exact representability question. Rank-product bounds and numerical algorithms alone do not establish its hardness.

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 rational matrix M and separate integer widths p and q, find real factors U,V,W,Z with M=(UV)⊙(WZ), where UV has rank at most p and WZ rank at most q, or report NO-SOLUTION. Signs are unrestricted and witnesses use a common real algebraic primitive-element encoding.

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 arbitrary real factorizations, not just the intended zero-pattern construction. Separate width bounds do not settle a total-rank budget.

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.