The $(2,1)$-Gapped Consecutive-Ones Property Problem is NP-complete
candidateconfidence 50%
VibeMathed reports this item as candidate. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Precise statement
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 source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement
fidelity, correctness, priority, or novelty.
What AI did
GPT-5.6 Sol High
GPT-5.6 Sol High produced the central NP-completeness construction: a polynomial-time reduction from 3-SAT using ordered slots, two-column variable gadgets, and a seven-column clause gadget implementing Boolean OR. The associated account reports that the solution emerged in roughly 3–4 model messages, with prompts written by the model for itself. The proof package includes exhaustive finite checks of the clause gadget and a separately implemented verifier/cross-check.
Checked by this site on 17 August 2026: the Zenodo record (21898823) is real, credited to Maciej Nowicki and "Eve" with the proof and verification package attached, and the prior-open status verifies - the Chauve-Manuch-Patterson hardness paper (arXiv:0912.0309) establishes the (k,delta)-C1P classification whose exceptional case this claims to close, and the linked 2011 follow-up restates it as open. The reduction itself was not checked here, and no independent review exists; a self-published record by a pseudonymous-branded author stays Candidate until the proof is checked by someone.
I proved the last open case of the Gapped Consecutive-Ones problem is NP-complete, and the key 7-column OR gadget is optimal
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.
Known method families
argument (source-reported)
Source-reported tools: argument.
Independent: unknown · difference confidence: 0
What remains uncertain
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.
The source status is candidate and must not be represented as solved.
VibeMath has not independently verified the mathematical claim.
AI-attempt independence and training-data exposure are unknown unless explicitly documented.
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.