1,076 problems

For a finite relational structure $\mathbb{A}$, let $CSP(\mathbb{A})$ denote the associated constraint satisfaction problem. Feder–Vardi dichotomy conjecture. The complexity of…

A label-cover instance consists of variables, an alphabet, and constraints between variable pairs; a constraint is bijective when each label on either variable determines exactly o…

The Exponential Time Hypothesis (ETH) is the hypothesis that $3$-SAT has no deterministic algorithm with running time subexponential in the number of variables. ETH. $3$-SAT admits…

Let $(\Gamma_n)_n$ be a sequence of planted subgraphs in the recovery model, and suppose there is a gap between the information-theoretic limit and the performance of the proposed…

Bodirsky–Pinsker conjecture. $\operatorname{CSP}(\mathbb C)$ is either in P or NP-complete.

Average-case hardness conjecture. Approximating the corresponding amplitudes up to a multiplicative error is $\textsc{\#P}$-hard on average. This conjecture concerns the average-ca…

Consider the planted clique problem in an Erdős–Rényi random graph on $n$ vertices, where the planted clique has size $k$. Planted clique conjecture. Recovery is computationally in…

Polynomial-time conjecture. Alternating link equivalence can be decided by a deterministic algorithm whose running time is polynomial in the size of the input diagrams.

A Boolean function is a map $f:[?{0,1}^n\rightarrow\{0,1\}$. Its sensitivity is the maximum, over inputs, of the number of coordinates whose change alters the function value; its d…

Geelen–Gerards–Whittle conjecture. For any minor-closed proper subclass of binary matroids, the minimum cut problem is in P.

Let $k$ be the order of a tensor, and consider noisy tensor completion for an order-$k$ tensor of dimension parameter $n$. A polynomial-time algorithm is an algorithm whose running…

Small Set Expansion hypothesis. For any $\varepsilon>0$, there is a constant $\delta\in(0,1)$ such that no polynomial-time algorithm can distinguish between the case…

The paper considers discrete diffusion models on a state space of dimension $d$, with computational complexity measured up to polylogarithmic factors using the notation…

VP versus VNP conjecture.

The Planted Clique problem asks whether an Erdős–Rényi graph on $n$ vertices contains a planted clique of size $k$. Planted Clique conjecture. There is no polynomial-time algorithm…

Let $s_{\lambda/\mu}$ and $s_{\nu/\rho}$ be skew Schur functions, and write $f\leqslant_s g$ when $g-f$ is Schur-positive. For skew shapes, the LPP inequality is … The complexity c…

Let $\Gamma_n$ be a complete bipartite planted subgraph with $k_{\mathsf{L}}$ left vertices and $k_{\mathsf{R}}$ right vertices, in an ambient graph on $n$ vertices. Complete bipar…

A promise CSP is specified by relational structures $(B,C)$ with a homomorphism from $B$ to $C$; $\operatorname{PCSP}(B,C)$ asks whether an input finite structure $A$ has a homomor…

OGP computational-hardness conjecture. OGP is a marker of computational hardness: instances with the OGP cannot be solved efficiently by the relevant algorithmic classes.

For every graph $H$, consider the problem $\textsc{H-Cover}$ of deciding whether an input graph covers $H$. Strong Dichotomy Conjecture. For every graph $H$, the problem…

Let $\mathbf{QS5}$ be the quantified modal logic QS5, and consider its fragment using two individual variables and a single unary predicate letter. Decidability conjecture. The fra…

Brakensiek–Guruswami conjecture. For every $k\geq 1$ and $n\geq 3$, the problem

Let $\mathcal{F}$ be a finite set of graphs, and let an $\mathcal{F}$-free graph be a graph with no induced subgraph isomorphic to a member of $\mathcal{F}$. Let $\mathcal{S}$ be t…

Let $G$ be a $2$-connected graph. For the forbidden linear ordering family consisting of $(G,\le)$, consider the problem of deciding, for an input graph $H$, whether there is an…

Proper-containment conjecture. Each of these containments is proper.