← All problems

Kleinschmidt–Onn partitionability problem

Given a finite pure dd-dimensional simplicial complex Δ\Delta, decide whether its face poset can be partitioned into Boolean intervals of the form [Ri,Fi]={G:Ri⊆G⊆Fi}[R_i,F_i]=\{G:R_i\subseteq G\subseteq F_i\}, where each FiF_i is a facet of Δ\Delta. Determine the computational complexity of this recognition problem for each fixed dimension dd, in particular whether it is solvable in polynomial time or is NP\mathrm{NP}-complete.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 NP\mathrm{NP}, since a proposed interval partition can be verified in polynomial time.
  • Recognition is known to lie in P\mathrm{P} for dimension at most two.
  • For fixed dimension d≥3d \ge 3, membership in P\mathrm{P} was previously not known; NP\mathrm{NP}-completeness had been conjectured for some dd.

October 2026 NP-completeness claim

Russ Woodroofe’s preprint Partitionability is NP-complete claims NP\mathrm{NP}-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 NP\mathrm{NP} and polynomial-time recognition in dimension at most two.

Sources

Solutions 0

No solutions have been posted yet.