3-SAT → Nonnegative integer rank two for 3×3 matrices Complexity open
Unsolved
Why this question matters
The question would distinguish arithmetic restrictions from real rank-two factorization in the smallest nontrivial matrix shape.
The known reduction compresses an arbitrary-size rank-two matrix to 3×3; it does not reduce 3-SAT to integer factorization. The paper’s search algorithm depends on entry magnitudes, not just their binary encoding lengths. No NP-hardness proof or polynomial bit-complexity algorithm for this restricted problem was located in the checked literature. Complexity open describes this classification gap; it is not an author-stated NP-hardness conjecture.
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 3×3 nonnegative integer matrix with binary-encoded entries of ordinary rank exactly two, find nonnegative integer U of size 3×2 and V of size 2×3 with M=UV, or report NO-SOLUTION.
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.
Scaling can change integer feasibility, so clearing rational denominators is not a valid substitute for an integer-preserving construction.
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-20. Checked on 2026-09-20: arXiv v2, Lemma 2.9, the construction preceding Theorem 2.10, Section 3.1, the conclusion and version history. Web searches covered the paper identifier, rank2 problem complexity, and nonnegative integer rank with NP-hardness and 3×3 restrictions. No resolving result was located. This is a bounded literature assessment, not an exhaustive novelty certificate.