Polynomial-time recognition conjecture for 0/1 slack matrices

Let S{0,1}m×nS\in\{0,1\}^{m\times n}. A matrix is a slack matrix if it is the slack matrix of a polytope. Polynomial-time recognition conjecture. There is an algorithm polynomial in m,nm,n that correctly determines whether SS is the slack matrix of a polytope. The conjecture concerns the unresolved complexity of recognizing slack matrices among 0/1-valued matrices, equivalently the recognition problem for 2-level polytopes.

Sources & referencesView supporting material

Primary source

Manuel Aprile, Michele Conforti, Yuri Faenza, Samuel Fiorini, Tony Huynh and Marco Macchia, “Slack matrices, k-products, and 2-level polytopes”, arXiv:2106.12829 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.