30 problems

Let $T$ be a tile in $\mathbb{Z}^n$. A tiling by translated copies of $T$ is periodic if it is invariant under a nonzero translation of $\mathbb{Z}^n$. Periodic tiling conjecture.…

Ollinger's conjecture. The $8$-polyomino tiling problem is undecidable.

Undecidability conjecture. The problem of deciding whether a given hyperbolic group has a finite quotient is undecidable. Equivalently, there exists a hyperbolic group which is not…

Consider constrained homogeneous random walks in ${\cal Z}_+^d$ and the associated problems of computing stationary probability distributions and large-deviation rates. The source…

A multiclass queueing network is a queueing system with multiple customer classes, and a priority or First-In-First-Out policy is a scheduling rule that selects which waiting custo…

Let $\mathsf{S}=\mathsf{S}_{\to,\land,\lor}$ be semilattice relevant logic in the signature $\{\to,\land,\lor\}$. Its decision problem asks whether there is an algorithm deciding,…

Cerlienco's conjecture. If $K=\mathbb{Q}$, then the property

A totally real field is a number field all of whose embeddings into the complex numbers have real image. J. Robinson's conjecture. The ring of integers of any totally real field ha…

An exponential Diophantine equation over $\mathbb Q$ is an equation built using variables, rational constants, arithmetic operations, and exponentiation with nonnegative base and e…

Tensor stable positivity conjecture. The set of yes-instances of tensor stable positivity, denoted $\textsc{tsp}$, is not recursively enumerable.

Asymptotic-capacity undecidability conjecture. The following problem is undecidable: given a partially fixed-size network $(V,E,\{A_v\},\{B_v\},s_M,s_E)$, decide whether its asympt…

A partially fixed-size network has vertex set $V$, edge set $E$, source-message sets $\\{A_v\\}$, demanded-message sets $\\{B_v\\}$, and size specifications $s_M$ and $s_E$. The sp…

A network coding instance consists of a finite network with messages and edges whose alphabet sizes are allowed to vary with a common alphabet-size parameter. Undecidability conjec…

Let $\mathcal{A}$ be an algorithm and $x$ an input. A $\otimes$-graph with cardinal inequalities is an $\otimes$-graph $\mathcal{G}$ equipped with cardinal inequalities between its…

Baker–Matijasevič–Robinson conjecture. The theory $\exists^3$ is undecidable over $\mathbb{N}$.

Let $P(x,y,z)\in\mathbb Z[x,y,z]$. Consider the equation … with integer variables $x,y,z$. Sun's squared-variable conjecture. There is no algorithm that determines, for every such…

For a polynomial $P(a,x_1,x_2,x_3)\in\mathbb Z[a,x_1,x_2,x_3]$, consider the quantified Diophantine statement … with variables ranging over $\mathbb N=\{0,1,2,\ldots\}$. Rojas's co…

Let $\mathcal{A}$ and $\mathcal{B}$ be automata, and let $\Sigma(\mathcal{A})$ and $\Sigma(\mathcal{B})$ be the automaton semigroups generated by their states. Their free product i…

An automaton semigroup is a semigroup generated by the states of a finite synchronous automaton, and the free product of semigroups $S$ and $T$ is denoted by $S\star T$. The automa…

Minimal interpretation-degree conjecture. There is no theory with a minimal degree of interpretation for which $\sf G1$ holds, $\langle \sf D, \lhd\rangle$ is not well founded, and…

Let $G$ be a group in one of the solvable-group classes considered in the paper. A ring is e-interpretable in $G$ if its structure can be interpreted in $G$ by systems of equations…

A ring of algebraic integers $O$ is the integral closure of $\mathbb Z$ in a finite field extension of $\mathbb Q$. The Diophantine problem in $O$, denoted $\mathcal{D}(O)$, asks w…

A rational Diophantine equation is a polynomial equation with rational coefficients whose variables are required to take rational values. Undecidability conjecture. There is no alg…

Let $Y$ be a finite nonpositively curved square complex. A square complex is virtually special if it has a finite-sheeted cover that is special. Bridson–Wilton's conjecture. There…

Let $\mathcal D$ be a strongly regular event domain. A regular nice labeling is the labeling property used in Thiagarajan's conjecture. Undecidability conjecture. There does not ex…