5 problems

Non-completeness conjecture. The IP-based model for {Sequencing to Minimize Tardy Tasks} is not $\textsf{NP-S}$-complete.

A tournament is a directed graph in which exactly one of the two possible directions is chosen for every pair of distinct vertices. For a tournament $T$, its directed clique number…

For fixed $m\geq 3$, consider short Presburger sentences … where the quantifiers alternate, each $\mathbf{x}_i\in\mathbb{Z}^{n_i}$ has fixed dimension, and $\Phi$ is a fixed Boolea…

Let $\mathrm{PH}$ denote the polynomial hierarchy, and let GVB denote the general variable branching problem. Stockmeyer's polynomial-hierarchy properness conjecture. The polynomia…

Polynomial-hierarchy non-collapse conjecture. The polynomial hierarchy does not collapse: each term in this union is larger than the previous one.