People who code: we want your input. Take the Survey

# Tag Info

17

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 no solution :-) The counting version is #P-hard: Graham R. Brightwell, Peter Winkler: Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005: 259-262

17

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 https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution. But counting the number ...

17

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 bipartite graph $G$ with left vertices $[n]$ and right vertices $[n]$, where the edge $(i,j)$ is present if and only if $M_{i,j}=1$. A perfect matching is a subset ...

15

There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.

11

Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible. See discussion in Monotone arithmetic circuits. A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

10

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} 1 & 0 & \dots & 0 \\ 0 & & & & \\ \dots & & M & &\\ 0 & & & & \end{bmatrix} It is ...

9

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(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\... 8 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 cycles" near the top of p. 417. Valiant gives a Turing reduction from the number of Hamiltonian cycles. 8 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 random vector with elements chosen from$\{0,1\}$, uniformly and independently. Note that$\operatorname{per}(M^+)=\operatorname{per}(M)$. Now consider Ryser's ... 8 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 have at least one linear extension b) How many does it have? #P-complete to determine this (Brightwell and Winkler, Counting Linear Extensions, Order, 1991) c) ... 8 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 inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit closure of the ... 8 I think this may have been a typo in Agrawal's paper. The best I know is how to write an$n \times n$determinant as a projection of an$O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer. 7 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-deterministic Turing Machine$M$, define its language$L(M)$to be the set of inputs$x$to$M$such that, among all non-deterministic executions of$M$on input$x$, ... 6 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 check if your formula is empty or not) but the counting problem is #P-hard. Even approximating the number of satisfying assignments of such formula is hard (see ... 6 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 decomposing doubly-stochastic matrices. The run-time bound comes from$O(n^2)$iterations of a procedure in which each iteration involves finding a matching, and ... 6 This is an (interesting) open problem, as far as I know. Rahul Santhanam and I explicitly mention the problem of proving Permanent is not in LOGSPACE-uniform TC0 in our CCC'13 paper (On Medium-Uniformity and Circuit Lower Bounds). 6 Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an$n\times n$matrix. The lower bound is$2^{2n - 0.25\log^2 n}$, and he notes that a formula of size$2^{2n - 0.25\log^2 n + O(\log n)}$exists (Theorem 3.1. and comment after the proof). The survey by Shpilka, and Yehudayoff is a good resource. Also, a ... 6 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. 5 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 constant depending on the constant in the input bit size), we know it outright. Your problem with$p$allowed to have$O(\log n)$bits is PP-hard under polynomial-... 5 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 (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.'' Let$\mathbb{F}$be a field and$\...

5

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 fact that the symmetries of the determinant characterize it). Whenever one has some determinantal identities, they can often be massaged into getting equations ...

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}{n+m}$. Also, the number of perfect matchings in $G'$ is exactly twice the number of perfect matchings in $G$, because the perfect matchings of $G'$ are the ...

2

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 least "extremely accurate" as they state it) samples from a certain distribution, then the polynomial hierarchy collapses up to some level. To prove the same ...

2

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 many perfect matchings as $G$ (see Theorem 6.2.). Then from $G'$ you can construct a graph $G''$ with average degree arbitrarily close to $2$ and twice as many ...

2

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 argument proves such an inclusion, i.e., there are oracles $X$ such that randomized polynomial-time with a $(\Sigma^P_{(\log n)^c})^X$ oracle does not include $\#P^X$....

2

The permanent of a 01-matrix is equal to the number of vertex cycle covers of an unweighted directed graph. Its computation is #P-complete.

1

I think this paper directly answers your question. Cancellation is exponentially powerful for computing the determinant Sengupta shows that even if you use subtraction (hence the circuit is not monotone) but as long as you never "cancel" any computed monomials, then the circuit computing determinant of the matrix of size $n \times n$ has size at least \$n(...

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