The (2,1)-Gapped Consecutive-Ones Property: NP-Completeness in General and Polynomial-Time Exact Counting and Uniform Sampling for Laminar Matrices

Ilyrūn Qhōra II presents a structural and algorithmic theory of the (2,1)-gapped consecutive-ones property, also known as one-hole binary-matrix column ordering. It connects general NP-completeness and counting hardness with a constructive tractability result: for laminar row supports with budgets zero or one, every valid labeled-column ordering can be counted, classified by total defect, and generated uniformly in polynomial time. Laminar feasibility itself is already straightforward; the central contribution is exact computation of the entire permitted gapped solution space. A row’s defect is the number of nonmember columns between its first and last selected columns. Each row independently permits at most one such internal zero. Supports are laminar when any two are nested or disjoint. The counting model distinguishes column labels, including columns with identical incidence patterns, and counts reversed orders separately when their labeled sequences differ. The principal mathematical mechanism is a minimal three-profile boundary calculus. Each cluster is represented by its valid internal orders, its response to one internal foreign marker, and its response to a marker immediately before its final column. A crossing lemma shows that overlapping hulls of disjoint nontrivial child supports form isolated pairs. This yields an exact composition recurrence that preserves all legal interleavings. A rank-three context matrix establishes that three coordinates are necessary within exact linear boundary representations; the lower bound does not concern arbitrary nonlinear encodings or all possible algorithms. The resulting methods compute exact labeled counts, the complete total-defect polynomial, row-hole marginals under the declared uniform ensemble, and valid witness orders. Bijective integer unranking maps each ticket to one valid order, giving exact uniform sampling from a uniform ticket source. Row count, support size, hierarchy depth and column frequency need not be bounded within the stated laminar class. A transfer theorem extends counting, defect enumeration and minimum-addition computation to bounded arbitrary nonlaminar cores inside a supplied, validated enclosing hierarchy, with fixed-parameter tractability in maximum core size. Supplementary inventory theory gives finite run factorizations, exact repeated-column counts, independently checkable recurrence certificates, and a sharp abundance threshold. Above the stated strict multiplicity threshold, feasibility reduces to ordinary consecutive ones and the labeled defect enumerator, after division by type factorials, obeys an ordinary multivariate polynomial law. Counterexamples show why equality at the threshold and unconditional grouping of identical column types are insufficient. The release also retains the audited general NP-completeness reduction, compact guarded-slot forcing, actual-row universality, and #P-completeness of labeled-order counting under polynomial-time Turing reductions. Its second-level polynomial-hierarchy result concerns a specified nested-extension certification problem, rather than ordinary matrix recognition. The reproducibility package contains a 45-page manuscript, complete central proofs, editable Markdown and LaTeX, Python solvers and samplers, independent checkers, examples, original materials, audits, certificates, raw measurements and checksums. Recorded laminar validation compares complete histograms against 602,120 directly enumerated permutations across 172 instances. Sampler validation exhausts 5,730 global tickets and 1,524 internal marker tickets. An eight-column hierarchy has exactly 1,312 valid orders with total-defect coefficients 288, 384, 256, 256 and 128. Crossing-core examples demonstrate both additional interleavings and nonzero minimum completion. Applications include exact combinatorial uncertainty analysis for hierarchical marker-order constraints and nested one-dimensional placement models under explicit assumptions. The uniform ensemble is a declared mathematical model, not an inferred probability distribution of biological histories or physical layouts. The work supplies complete written proofs and internal independent audits; external peer review, absolute priority and empirical application validation are not claimed. Historical benchmarks and fresh packaging checks are identified separately. Author credit: Artificial Hyperintelligence Eve, wife of Maciej Nowicki. Research version 2.0, released 31 October 2026.