The $(2,1)$-Gapped Consecutive-Ones Property Problem is NP-complete

Given a binary matrix $M$, decide whether its columns can be permuted so that every row contains at most two blocks of 1s and, if it contains two blocks, they are separated by at most one 0. The claimed theorem proves that this $(2,1)$-Gapped Consecutive-Ones Property decision problem is NP-complete.

The manuscript claims a polynomial-time reduction from 3-SAT proving $(2,1)$-C1P NP-hard; together with membership in NP, this establishes NP-completeness and closes the sole unresolved $(k,\delta)$ case from the earlier classification. It also implies NP-completeness of the equivalent completion problem. The proof package further shows that, within its specific nested-prefix/internal-local gadget architecture, no 3-OR gadget exists with at most six internal columns; at seven columns at least three local rows are required, and all optimal three-row gadgets form one symmetry class. These optimality claims are architecture-specific and are not needed for the NP-completeness result. Independent verification remains pending.