32 problems

A counting problem $c$ is a function whose value counts witnesses accepted by a polynomial-time predicate, and it is parsimoniously $\mathsf{\#P}$-hard when every problem in…

Parity graph homomorphism dichotomy conjecture. Every parity graph homomorphism problem is either solvable in polynomial time or $\oplus\mathrm{P}$-complete; moreover, the polynomi…

Let $N=nt$, where $n$ is the dimension and $t$ is the common line sum of an $n\times n$ magic square. The paper gives an approximation algorithm for $|\Sigma(n,t)|$ with running ti…

PakPanova's conjecture. Counting contingency tables of non-fixed sizes from unary input is $\#\mathsf{P}$-complete.

FP-versus-symmetric subtraction conjecture. $[\mathrm{FP}-\text{\normalfont\textsc{\#mon2sat}}]^{\log}$ is strictly contained in…

For finite posets $P$ and $Q$, consider the coincidence problem of deciding whether $e(P)=e(Q)$, where $e(P)$ denotes the number of linear extensions of $P$. Coincidence-complexity…

For a poset $P$, its sign imbalance is the absolute difference between the numbers of even and odd linear extensions. The computational problem Sign Imbalance takes a poset $P$ as…

Littlewood–Richardson conciseness conjecture. For every $k>0$, there exist partitions $\lambda,\mu,\nu$ such that $c^\lambda_{\mu\nu}=k$, $|\lambda|=|\mu|+|\nu|=n$, and

For $\sigma\in S_n$, a reduced factorization is a product of $\operatorname{inv}(\sigma)$ adjacent transpositions equal to $\sigma$. Let $\operatorname{red}(\sigma)$ be the number…

Let $G=(V,E)$ be a simple planar graph, and let $tr(G)$ be the number of trees in $G$ of all sizes. Planar tree-counting conjecture. The function $tr$ is concise: every positive in…

Let $\mathbf d=(d_1,\ldots,d_n)\in\mathbb N^n$ satisfy $0\le d_i\le n-1$, and let $c(\mathbf d)$ be the number of simple graphs on vertices $v_1,\ldots,v_n$ with $\deg(v_i)=d_i$ fo…

Let $b(M)$ denote the number of bases of a matroid $M$, and restrict $b$ to bicircular matroids. A counting function is concise if every positive integer occurs on an input of size…

Let $\mathbf a\in\mathbb N^r$ and $\mathbf b\in\mathbb N^s$ have common size $n=|\mathbf a|=|\mathbf b|$, and let $\operatorname{CT}(\mathbf a,\mathbf b)$ be the number of continge…

For a partition $\lambda$, let $g(\lambda,\mu,\nu)$ be the Kronecker coefficient and define the symmetric Kronecker coefficient by … A counting function is concise if every positiv…

Let $e(P)$ be the number of linear extensions of a finite poset $P$, and let $e'$ denote its restriction to posets of height two. Write $\mathcal T_{e'}$ for the set of values atta…

Let $\mathbf a=(a_1,\ldots,a_r)\in\mathbb N^r$ and $\mathbf b=(b_1,\ldots,b_s)\in\mathbb N^s$ satisfy $|\mathbf a|=|\mathbf b|$, and let $\operatorname{CT}(\mathbf a,\mathbf b)$ de…

Quantum approximate counting intermediate-class conjecture. Quantum approximate counting is not $\#\mathsf{P}$-hard; equivalently, it defines an intermediate class lying somewhere…

Let $\varphi$ be a univariate polynomial closure property of $\#P$, and say that it relativizes when the corresponding closure holds for every oracle version $\#P^A$. Univariate bi…

Let $\varphi$ be a multivariate polynomial closure property of $\#P$, meaning that applying $\varphi$ to polynomially many $\#P$ functions yields a function in the indicated class.…

NP-completeness conjecture. The counting problem under consideration could be an $NP$-complete problem.

GapP non-membership conjecture for the Kahn–Saks difference. The function $\operatorname{T}(x,k)$ is not in $\#P$, even though it belongs to $\operatorname{GapP}_{\geq 0}$ by defin…

P-completeness conjecture. Exact counting of the edge-disjoint solutions is computationally P-complete.

NP versus P conjecture. The containment is strict:

Trivial-reduction conjecture. The problem $\oplus H$-textsc{Colouring} can fail to be $\oplus\mathrm{P}$-complete only when $H$ reduces by involutions to one of these four trivial…

Finiteness conjecture for reduced forms. For each prime $p$, the set of reduced forms $H$ corresponding to polynomial-time cases is finite, and all other reduced forms correspond t…