336 problems

Hendrych's NP-hardness conjecture. The Bayesian AOD problem is NP-hard. This conjecture is resolved in the source: the paper proves NP-hardness for its regularized A-optimal design…

The Fooling-Set-Submatrix problem takes integers $n,m$ and an $m\times m$ $0/1$-matrix $A$ as input, and asks whether $A$ contains a fooling-set submatrix of size $n$. NP-hardness…

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$, and let $i\leq p$ and $j\leq q$. Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic…

Let $G$ be a circle graph, and let $I(G)$ be its independence complex. The size of the input is measured by the number of vertices of $G$. Polynomial-time homotopy-type conjecture.…

Bang-Jensen et al.'s complexity conjecture. Deciding whether a given digraph $D$ has inversion number at most $k$ is NP-complete for any fixed positive integer $k$.

Polynomial-time computation conjecture. There exists a polynomial-time algorithm to compute $\nu$ within arbitrary precision.

APUD(1,1) recognition conjecture. Given a graph $G$, it can be determined whether $G\in\mathrm{APUD}(1,1)$ in polynomial time.

NP-hardness conjecture. It is NP-hard to decide if a given $N$-bit vector $f=(1,f_0,\ldots,f_{d-1})$ of positive integers is the $f$-vector of a $d$-polytope.

Let $\mathsf{M}(\bm W)$ denote the Sherrington–Kirkpatrick Hamiltonian instance with random matrix $\bm W$, and let $c(\bm W)$ be the approximation ratio certified by an algorithm.…

Polynomial-time k-colouring conjecture. There is a polynomial-time algorithm that, given $G$, finds a $k$-colouring of $G$, or determines that none exists.

Polynomial-time dimension conjecture. The dimension of a poset given its linear extension graph can be determined in polynomial time.

Let $A$ be an integer matrix with columns ${\boldsymbol v}_1,\ldots,{\boldsymbol v}_n\in\mathbb{Z}^m$, let … and set ${\boldsymbol v}={\boldsymbol v}_1+\cdots+{\boldsymbol v}_n$. L…

Let $G$ be a graph, and let $\sigma(G)$ denote the minimum number of equivalence relations needed to cover the line graph structure under the paper's definition. For an integer…

Let a straight-line program for a polynomial in one variable be a list … where each $s_i$, for $i\geq 2$, is one of $s_j+s_k$, $s_j-s_k$, or $s_js_k$ for some $j,k<i$. For…

A Diophantine prefix is generically decidable when an algorithm decides the corresponding positive-integer Diophantine sentences on the restricted collection of inputs specified by…

Let $D$ be a finite set of positive integers, and let $\chi(D)$ denote the chromatic number of the distance graph with distance set $D$. For a fixed integer $k\ge3$, consider the d…

Let $d\geq 3$ be the maximum degree, let $\ell$ be the activity, and let $\ell_c(d)=(d-1)^{d-1}/(d-2)^d$ be the critical activity for decay of correlations on the infinite $d$-regu…

Birget's conjecture. There is a nondeterministic symmetric Turing machine accepting the language of words $w$ representing $1$ in $G$ within space

Let $\mathcal{F}$ be the family of polynomial systems $F$ such that $Z(F)$ is finite and the Galois group of $F$ over $\mathbb{Q}$ is dihedral or bicyclic. Let…

Let $F_r$ be a free group, let $NMin\subset F_r$ be the set of non-minimal elements, and let $WC(w)$ denote Whitehead complexity. Polynomial Whitehead-descent time-complexity conje…

Let $F_r$ be a free group, and let $T=T_r$ be the restricted set of Whitehead automorphisms described in the source. For each length $l$, let $NMin_l\subset F_r$ be the set of non-…

Let $K_n$ be the complete graph on $n$ vertices, let $\mathrm{Ramsey}(n,n)$ be the symmetric binary Ramsey number, and let $K_{\mathrm{Ramsey}(n,n)}$ be the complete graph on that…

Let $K_k$ and $K_n$ be complete graphs, let $E^r$ and $E^g$ be precolored red and green edge sets, and let $\mathrm{Ramsey}(n,n)$ denote the classic symmetric binary Ramsey number.…

Let $K_n$ be the complete graph on $n$ vertices, let $A$ be the achievement graph, and let $E^r$ and $E^g$ be the precolored red and green edge sets. Achievement-game tractability…

Let $G$ be a graph and let $A$ be the achievement graph, with no precolored red or green edges, denoted by $(G,A,\{\},\{\})$. Unrestricted graph Ramsey-game conjecture. Graph Ramse…