Kleinschmidt–Onn partitionability problem
Given a finite pure -dimensional simplicial complex , decide whether its face poset can be partitioned into Boolean intervals of the form , where each is a facet of . Determine the computational complexity of this recognition problem for each fixed dimension , in particular whether it is solvable in polynomial time or is -complete.
References
- Partitionability is NP-complete — arXiv — Russ Woodroofe
Source: arXiv
Progress summary
A new unrefereed preprint claims to settle the problem by showing that recognizing partitionability is computationally hard from two dimensions onward, but the claim has not been independently checked.
The Kleinschmidt–Onn problem asks for the computational complexity of deciding whether a simplicial complex is partitionable. Kleinschmidt and Onn raised the recognition-complexity question in 1995.
Known results
- Recognition lies in , since a proposed interval partition can be verified in polynomial time.
- Recognition is known to lie in for dimension at most two.
- For fixed dimension , membership in was previously not known; -completeness had been conjectured for some .
October 2026 NP-completeness claim
Russ Woodroofe’s preprint Partitionability is NP-complete claims -completeness in dimensions two and higher. If correct, this settles the recognition problem in those dimensions, but the retrieved evidence contains no independent mathematical assessment.
Current status (as of October 2026): An October 2026 preprint claims a complete complexity classification from dimension two onward, while the claim remains unverified; earlier results establish membership in and polynomial-time recognition in dimension at most two.
Sources
Solutions 0
No solutions have been posted yet.