Universality and recognition barriers for the(2,1)-gapped consecutive-ones property
Maciej Nowicki, Artificial Hyperintelligence Eve
Abstract
We prove a representation theorem and a sharp barrier to structural recognition for the one
hole consecutive-ones problem. Every upward-closed Boolean predicate with a polynomial
time verifier can be compiled, with polynomial explicit size, into actual binary-matrix rows
of total internal-zero budget one and strictly nested prefix interfaces. Conversely, every uni
formly polynomial-size family of such modules defines an upward-closed NP predicate. The
construction preserves witnesses and realizes arbitrary finite intersection complexes of zero
defect domains.
The principal consequence is a second-level completeness theorem stated entirely in terms
of binary matrices. For every fixed r≥2, given a feasible base matrix and strictly nested ad
ditional unit-budget rows, deciding whether every infeasible subfamily contains an infeasible
subfamily of at most r rows is Π₂ᴾ-complete. Hardness persists when the base and every
individual extension have explicit feasible orders, and all compatibility information through
order r follows a fixed pattern. This goes beyond proving that pairwise consistency can fail:
it characterizes the difficulty of certifying that bounded-order consistency is sufficient.
The construction rests on an independently audited assignment-faithful NP-completeness re
duction. Four rows force every slot of size q≥3, optimally within the stated guard-omitting
class, reducing the scaffold from 5n+21m to 5n+10m rows without changing its 3n+8m+1
columns. An exact endpoint-charge identity compiles certified block orders into weighted
finite-domain constraint systems for decision, counting, and minimum additions. A sepa
rate open-row dynamic program works without a supplied scaffold. We also establish #P
completeness of counting valid labeled-column orders under polynomial-time Turing reduc
tions, correcting for unequal clause multiplicities by interpolation.
The release includes complete proofs, executable compilers and exact recognizers, an inde
pendent direct-zero checker, fresh global reduction tests, portable certificates for selected
infeasible cases, a reproducible 24-instance benchmark, and two exact scientific examples.
Prior Helly and endpoint methods are attributed to Patterson and to Chepoi, Creignou, Her
mann and Salzer; standard CSP machinery is not claimed as new. Computational validation
and external review are distinguished from mathematical proof.