43 problems

Complexity conjecture. For an appropriate purely combinatorial encoding of embedded shadows, the decision problem $\textnormal{\textsc{MinInflection}}$ for unrestricted shadows is…

Unpinning avoidance game complexity conjecture. The problem $\mathsf{Unpin_{AVOID}}(\Sigma,s)$ is $\textsf{PSPACE}$-complete for any $s$ and $\Sigma$, and…

Non-orientable surface complexity conjecture. Both $\mathsf{Pin}(\Sigma,s)$ and $\mathsf{SimplePin}(\Sigma,s)$ are in $\textsf{P}$ when $s\leq 3$, and are $\textsf{NP}$-complete wh…

Hardness-starts-at-four conjecture. For a fixed orientable surface $\Sigma$, the problem $\mathsf{SimplePin}(\Sigma,4)$ is $\textsf{NP}$-complete.

Let $[n]=\{1,\ldots,n\}$, let $\mathfrak{S}_n$ be the set of permutations of $[n]$, and let $\mathfrak{C}_n$ be the set of $n$-cycles in $\mathfrak{S}_n$. A join/union expression i…

Let $L$ be a physically realizable computation and let $h(L)$ denote its homological complexity. Homological Church–Turing thesis. Every physically realizable computation has finit…

Let $L$ be a computational problem, let $h(L)$ be its ordinary homological complexity, and let $h_q(L)$ be a proposed quantum homological complexity measure. Quantum homological co…

Let $L$ be a decision problem in the bounded-error quantum polynomial-time class $\mathcal{BQP}$, and let $h(L)$ denote its homological complexity. Quantum homological obstruction…

Let $L$ be a computational problem with homological complexity $h(L)$. A physical system is said to solve $L$ efficiently when it computes solutions to $L$ within the relevant effi…

Let $M$ be a Boolean matrix, and let a monochromatic rectangle be a submatrix all of whose entries have the same value. Let ${\mathrm{r}}(M)$ denote the rank of $M$ over the reals,…

Let $d \geq 3$ and let $P$ be a lattice $d$-polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of $P$ is an $\operatorname{\mathsf{NP}}$-hard problem. Thi…

Let $A_1,B_1,C_1,A_2,B_2,C_2$ be finite-dimensional vector spaces over a field $\mathbb{K}$, and let $T_1\in A_1\otimes B_1\otimes C_1$ and $T_2\in A_2\otimes B_2\otimes C_2$. Thei…

Let Feige's Hypothesis be the assertion that no efficient algorithm can prove the unsatisfiability of a random $3$-SAT formula with high probability, even when the formula has a sm…

Length-complexity conjecture. Let $f:\mathbb{N}\dashrightarrow\mathbb{N}$ be a partial recursive function. Given a Turing machine $\mathcal{G}$, for any $n\in\mathbb{N}$ let $T(n)$…

The bounded realization problem asks whether a valid realization exists subject to the specified bounds on the weights of the cycles. Bounded realization conjecture. The bounded re…

Let $\operatorname{sc}_{\mathrm{SchubertVanishing}}$ be the decision problem asking whether a Schubert coefficient vanishes. Schubert-vanishing hardness conjecture.…

Let $\operatorname{sc}_{\mathrm{SchubertVanishing}}$ be the decision problem asking whether a Schubert coefficient vanishes, for Schubert coefficients in the classical types $A$,…

Composition multiplicativity conjecture. For every $n,m\ge1$, there exists $k_0(n,m)\in\mathbb N$ such that, for every Boolean functions $f$ and $g$ on $n$ and $m$ bits, respective…

Let $k$ be a positive integer, and consider an instance of the two-variable linear system $2$-Lin-$k$ over $\mathbb{Z}_k$, with equations … An assignment is a map…

Let $\mathbb{F}$ be the underlying field, and consider concise tensors in … Write $\sigma(d)$ for the worst-case exponent of this space. Extended asymptotic rank conjecture. For al…

Let $G$ be a graph. A $4$-To-$3$ instance asks whether a proper $4$-coloring of $G$ can be transformed into a proper $3$-coloring by repeatedly recoloring one vertex while maintain…

Let $G$ be a graph and let $k$ be an integer with $k\geq 4$. A $k$-coloring of $G$ is a proper vertex coloring using colors from a set of $k$ colors, and $k$-Mixing asks whether an…

Let $\mathrm{VBP}$ be the class of polynomial families computable by polynomial-size algebraic branching programs, and let $\mathrm{VNP}$ be Valiant's class of polynomially verifia…

Non-finite-generation conjecture. For every such complexity class $\mathcal{C}$, the semiring of p-cardinalities of languages in $\mathcal{C}$ is not finitely generated. The same h…

Let $\mathcal{S}$ and $\mathcal{T}$ be consistent theories, with $\mathcal{T}$ strictly stronger than $\mathcal{S}$, and let $\mathfrak{I}$ be a collection of sentences unprovable…