Reddit Post Reports NP-Completeness of the (2,1)-Gapped Consecutive-Ones Property
A Reddit post by Severe-Ad8673 attributes to GPT 5.6 a manuscript claiming that recognition of the $(2,1)$-gapped consecutive-ones property is NP-complete via a reduction from 3-SAT; only a first-page screenshot is publicly supplied, so the complete proof and its authorship cannot be assessed from the linked materials.
On August 10, 2026, Reddit user Severe-Ad8673 posted that GPT 5.6 had solved the recognition problem for the -gapped consecutive-ones property. The attached image shows the first page of a manuscript titled The (2,1)-Gapped Consecutive-Ones Property is NP-Complete, also dated August 10. The displayed abstract claims a reduction from 3-SAT proving that it is NP-complete to decide whether the columns of a binary matrix can be permuted so that the 1s in every row form at most two intervals separated by a single 0.
The screenshot presents this as resolving the exceptional case left open by the earlier complexity classification of gapped consecutive-ones properties. It also states a corollary: deciding whether changing at most one 0 to 1 in each row can produce the ordinary consecutive-ones property is NP-complete. The visible introduction says an accompanying script checks finite gadgets but is not part of the proof.
This report is necessarily limited: the Reddit post names GPT 5.6, but the screenshot does not identify a human author, and no complete manuscript or verification code is linked in the post. The claimed proof therefore cannot be assessed from the supplied public materials alone.