Skip to main content
Share Your Experience: Take the 2024 Developer Survey
17 votes

Easy problems with hard counting versions

A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph. The decision version is easy (... and the Seven Bridges of Königsberg problem has ...
Marzio De Biasi's user avatar
17 votes

Easy problems with hard counting versions

One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
Jeffrey Shallit's user avatar
10 votes
Accepted

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

This is unlikely to be NP-complete, as it can be solved in coRP, using a few calls to PIT. (It follows that this problem is not NP-complete unless $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{PH} = \...
Joshua Grochow's user avatar
10 votes
Accepted

Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

Your problem is equivalent to testing, given $M$, whether $PER(M) > 0$. Proof: Assume you are given $M$ and you want to decide whether $PER(M) > 0$. We construct $M'$ as follows: \begin{bmatrix}...
holf's user avatar
  • 2,174
9 votes
Accepted

Easy problems with hard counting versions

Here's a truly excellent example (I may be biased). Given a partially ordered set: a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets ...
Gara Pruesse's user avatar
9 votes
Accepted

Complexity of computing generalised determinants. (P - #P transition)

I extend my comment in an answer. By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\...
holf's user avatar
  • 2,174
8 votes
Accepted

Complexity of permanent verification

At the very least, the problem is "hard for the polynomial hierarchy" in the following sense. Let $PermVerify$ be the problem specified. Then $$PH \subseteq P^{\#P} \subseteq NP^{PermVerify}$...
Ryan Williams's user avatar
8 votes

Is #CYCLE #P-complete?

This is one of the problems (very briefly) discussed by Valiant, "The Complexity of Enumeration and Reliability Problems", SIAM J. Comput. 1979, doi:10.1137/0208032. See the mention of "elementary ...
David Eppstein's user avatar
8 votes
Accepted

On complexity of permanent ${}\bmod 2^t$?

One can compute it in $\sum_{i=0}^{t-1} \binom{n}{i}n^3$ expected time. Consider a $(n+1)\times(n+1)$ matrix $M^+ = \left[\begin{array}{ll} M & v \\ 0 & 1 \end{array}\right],$ where $v$ is a ...
Andreas Björklund's user avatar
7 votes
Accepted

Can we decide whether a permanent has a unique term?

EDIT - 2/11/20 - barring mistakes, this should answer the posted question. Summary. Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-...
Neal Young's user avatar
  • 10.8k
6 votes

Easy problems with hard counting versions

Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to ...
holf's user avatar
  • 2,174
5 votes
Accepted

Complexity of permanent modulo prime

First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied ...
Emil Jeřábek's user avatar
5 votes

Easy problems with hard counting versions

From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point From the abstract: ``This is the only natural computational problem where determining the existence of an object (...
Daniel Apon's user avatar
  • 6,011
5 votes
Accepted

Application of weak determinantal identities to GCT?

Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the ...
Joshua Grochow's user avatar
4 votes
Accepted

Is Permanent $+$-reducible?

If you allow weighted edges and weighted perfect matchings (instead of just counts), then yes. I don't know a "nice" clean graph-theoretic description, but in principle one can be extracted ...
Joshua Grochow's user avatar
3 votes
Accepted

What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

You can take any degree 3 bipartite graph $G$ and take its disjoint union $G'$ with a cycle $C$ of length 2m. The new graph $G'$ is bipartite, and has average degree $\frac{3n + 2m}{m+n} = 2 + \frac{n}...
Sasho Nikolov's user avatar
2 votes

Computational hardness for sampling a uniform matching

Concerning your general question, I think the paper by Aaronson and Arkhipov [1] on boson sampling is a good example. They show that if there exists a classical poly-time algorithm that exactly (or at ...
smapers's user avatar
  • 849
2 votes
Accepted

Approximating max degree $3$ perfect matching count?

Dagum and Luby show (using a construction credited to Dahlhaus and Karpinski) how to construct, given a bipartite graph $G$, a bipartite graph $G'$ of maximum degree $3$ such that $G'$ has exactly as ...
Sasho Nikolov's user avatar
2 votes

On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?

This is very unlikely to hold, but (as usual) impossible to rule out using current techniques, as we can’t even prove $\mathit{PSPACE}\ne P$. However, we can at least show that no relativizing ...
Emil Jeřábek's user avatar
1 vote

Permanent of doubly stochastic matrix

Van der Waerden's conjecture, proved by Egorychev and Falikman, gives a lower bound on the value of the permanent of doubly stochastic matrices. Linial,Samorodnitsky and Widgerson (2000) use that to ...
ricardorr's user avatar
  • 561

Only top scored, non community-wiki answers of a minimum length are eligible