The -Gapped Consecutive-Ones Property Problem is NP-complete
Given a binary matrix , 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 -Gapped Consecutive-Ones Property decision problem is NP-complete.
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Computational complexity / consecutive-ones property
- Posed by
- Cédric Chauve, Ján Maňuch, Murray Patterson
- Year posed
- 2009
- Years open
- 17y
- Solved
- 2026-08-12
- Model
- GPT-5.6 Sol High
- Vendor
- OpenAI
- Collaborators
- Maciej Nowicki
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The manuscript claims a polynomial-time reduction from 3-SAT proving -C1P NP-hard; together with membership in NP, this establishes NP-completeness and closes the sole unresolved 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.
What the AI did
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.
Verification
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.
Sources
- PaperI proved the last open case of the Gapped Consecutive-Ones problem is NP-complete, and the key 7-column OR gadget is optimalOriginal 2009 hardness paper leaving $(2,1)$-C1P open2011 follow-up explicitly stating that $(2,1)$-C1P remains openInitial Zenodo record announcing the NP-completeness proof
Submitted by LucidHawk551 on