23
The most recent paper on this question seems to be:
Noam Livne, A note on #P-completeness of NP-witnessing relations,
Information Processing Letters, Volume 109, Issue 5, 15 February 2009, Pages 259–261
http://www.sciencedirect.com/science/article/pii/S0020019008003141
which gives some sufficient conditions.
Interestingly the introduction states "To date,...
20
There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. Vassilevska and Williams, 2009.
20
This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph).
[1] Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.
19
The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in:
Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421 (1979)
From the paper:
...
4. Some #P-complete problems
...
14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected)
Input: $G; s,t \...
18
Counting the number of s,t-cuts is #P-complete. This is a result by Provan and Ball.
J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)
Therefore, unless some complexity-theoretic collapse happens, you cannot get essentially faster algorithm ...
18
It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007).
B. Roberts and D. P. Kroese, "Estimating the number of $s$--$t$ paths in a graph". Journal of Graph Algorithms and Applications, 11(1):195-214, 2007.
L. G. Valiant, "The ...
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
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
16
This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.
Here are the first few lines of his answer. To read the complete answer, follow the link.
There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n ...
15
An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see
Holger Dell, Thore Husfeldt, and Martin Wahlén.
Exponential time complexity of the permanent and the Tutte polynomial.
Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/
That is, if ...
15
#3-Regular Bipartite Planar Vertex Cover is #P-Complete
As counting vertex covers is exactly the same as counting satisfying assignments of a monotone #2-SAT instance, the above result implies that it is #P-complete to count satisfying assignments of a #2-SAT instance which is monotone and 3-regular and bipartite and planar.
This in turn means that, in ...
15
I think that whether p>0 can be decided in polynomial time.
The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting of m+1 layers each of which contains n vertices, plus m degree-4 vertices to represent the possible adjacent swaps. Note that the planarity of this graph ...
14
If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of accepting paths of an NP verifier.)
This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case ...
14
This problem is Monotone-SAT. It is #P-Complete under Cook Reductions. It is one of those problems that are "easy to decide but hard to count." I recommend the following paper. Self-Reducibility of Hard Counting Problems
with Decision Version in P
13
Something that has not been mentioned so far (as far as I can see) and that holds in the unrelativized world is the following:
$$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$$
This was observed by Vyalyi in this paper and comes from the strengthening of two theorems:
Toda's theorem - Vyalyi shows that one query to a $\sharp P$ oracle is enough for a "$...
13
The output number of paths may be $\Omega(2^N/n)$ (choose $s$ arbitrarily and then choose $t$ as the vertex that is the endpoint of the largest number of the $2^N$ walks from $s$) which requires $\Omega(N)$ bits to write down explicitly; this is exponential in the input size. On the other hand, the matrix powering approach has complexity polynomial in the ...
13
It is known that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.
13
Assuming $\mathsf{PH}$ does not collapse and that Graph Isomorphism is not in $\mathsf{P}$, then $\# GI$ (the counting version of graph isomorphism) satisfies your conditions. This is because $\# GI \equiv_m^p GI$.
13
The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete.
This has been proved by Les Valiant himself, on page 415 of the paper
Leslie G. Valiant
The Complexity of Enumeration and Reliability Problems
SIAM J. Comput., 8(3), 410–421
11
You have some fundamental misunderstanding of what a language $L$ being in $\mathsf{NP} \cap \mathsf{coNP}$ means. You'd need to show that there exist two machines: $M$ which is an $\mathsf{NP}$ machine, and $M'$, which is a $\mathsf{coNP}$ machine, such that $L$ is decided by $M$, and $L$ is also decided by $M'$. Each one should be able to solve the problem ...
11
Perhaps this paper can help you:
New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter by J. Zhou, M. Yin, C. Zhou (2010).
And this one that studies the structure of the set of solutions of a random 2-SAT instance: Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps by G. ...
11
This topic has been extensively investigated in recent years under the name of Holographic Algorithms by researchers such as Valiant, Cai, Lu, Xia, Lipton, and others. Essentially all tractable cases of #CSP (counting constraint satisfaction problems) have been identified in terms of dichotomy theorems (FP vs. #P-complete). In particular, Matchgate ...
11
One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.
11
I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems.
EdgeCover is included in the dichotomy theorem in (1). Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs. To see ...
11
There has been a series of breakthroughs on Dichotomy Theorems by Professor Jin-Yi Cai https://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/
Another dichotomy theorem https://rjlipton.wordpress.com/2014/06/23/counting-edge-colorings-is-hard/
https://rjlipton.wordpress.com/2011/02/14/classifying-papers-on-classifying-...
11
Well, at least $\#\mathsf{P}$-hard. Given a SAT formula, construct a graph with two vertices, $v_x$ and $v_x'$, for every possible assignment of variables $\vec{x}$. If $x$ is a satisfying assignment for the formula, draw an edge between $v_x$ and $v_x'$; these are the only edges. It is easy to construct the circuit for this graph from the SAT formula, and ...
10
A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals. The problem flips from being trivially easy (always satisfiable) to being NP-complete by adding one to the associated parameter.
Let $f(k)$ denote the largest number such that any X$k$...
10
This post discusses #P-completeness of #Monotone-2SAT under weakly parsimonious reductions. If you negate all literals in a monotone 2-CNF formula $\phi$, you obtain a Horn 2-CNF formula $\psi$ with the same number of satisfying assignments.
10
We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.
Here are some basic results for this:
Case 1: $k=2^{n-1}-\mathrm{poly}(n)$
Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\...
Only top voted, non community-wiki answers of a minimum length are eligible
