The NP-completeness conjecture for the Sigma-1 theory of Young's lattice

Let Y=P,\textbf{Y}=\left\langle \mathcal P,\leq\right\rangle be Young's lattice, where P\mathcal P is the set of partitions ordered by inclusion of their Young diagrams. The Sigma-1 theory conjecture. The Σ1\Sigma_1-theory of Young's lattice Y=P,\textbf{Y}=\left\langle \mathcal P,\leq\right\rangle is NP\textbf{NP}-complete. The preceding discussion establishes that this theory is at least NP\textbf{NP}-hard if it is decidable; the conjecture asks for the matching upper bound. An affirmative answer would give an NP\textbf{NP}-characterization of the posets that embed in Young's lattice.

Sources & referencesView supporting material

Primary source

Alexander Wires, “Complexity in Young's Lattice”, arXiv:1907.13360 (2019).

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.