Discoveries / theoretical-computer-science

The $(2,1)$-Gapped Consecutive-Ones Property 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.