The (2,1)-Gapped Consecutive-Ones Property Problem is NP-complete
Statement
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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
GPT-5.6 Sol High, with Maciej NowickiThe record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.