The NP-completeness conjecture for the Sigma-1 theory of Young's lattice
The NP-completeness conjecture for the Sigma-1 theory of Young's lattice
Let be Young's lattice, where is the set of partitions ordered by inclusion of their Young diagrams. The Sigma-1 theory conjecture. The -theory of Young's lattice is -complete. The preceding discussion establishes that this theory is at least -hard if it is decidable; the conjecture asks for the matching upper bound. An affirmative answer would give an -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.