17
votes
Accepted
Matrix permanent is 0
Expanding my comment:
Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1.
We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a ...
- 2,803
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 ...
- 22.6k
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 ...
- 6,967
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} = \...
- 36.9k
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}...
- 2,164
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 ...
- 342
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(\...
- 2,164
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}$...
- 27.3k
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 ...
- 50.9k
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 ...
- 3,254
8
votes
Accepted
Implications of a recent negative result to geometric complexity
It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an ...
- 36.9k
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-...
- 9,595
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 ...
- 2,164
6
votes
Accepted
The complexity of decomposing a bi-stochastic matrix
Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for ...
- 8,821
6
votes
Matrix permanent is 0
If it suffices to know the parity of the permanent, you can compute it in polynomial time by computing the determinant of the matrix over the field of size 2.
- 962
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 ...
- 16.9k
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 (...
- 5,961
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 ...
- 36.9k
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 ...
- 36.9k
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}...
- 18.1k
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 ...
- 16.9k
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 ...
- 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 ...
- 18.1k
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 ...
- 541
Only top scored, non community-wiki answers of a minimum length are eligible