21
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
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 ...
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 \...
17
Hopefully the following paper finally resolves this question: it says that MAJORITY 3SAT is in polynomial time. (And it proves a bunch of other unexpected results on related problems.)
https://arxiv.org/abs/2107.02748
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
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
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$.
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
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
13
You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious.
For the record, here's a sketch of a reduction that is parsimonious.
It is obtained by composing parsimonious reductions from 3-SAT to 1-in-3-SAT, from 1-in-3-SAT to a problem we call 1+3DM, and from 1+3DM to 3DM. We sketch each of these next.
Lemma 1. There is a ...
12
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 $\...
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
One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.
10
By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is not in PP then E has subexponential-size circuits with PP gates. That is consistent with the fact that an oracle proof of PH not in PP gives a relativized lower ...
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
Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in $O^*(2^k)$ with a randomized algorithm or $O^*(2.62^k)$ deterministically.
This is while Counting $k$-paths is $\#W[1]$-hard.
A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
...
10
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
It is shown to be $\oplus P$-complete by Faben:
https://arxiv.org/abs/0809.1836
See Thm 3.5. Note that counting independent sets is same as counting solutions to monotone 2CNF.
9
I you’re looking for natural problems, you can compute many counting problems on planar graphs in time $\exp(\sqrt n)$ because of the planar separator theorem. For example, everything that can be expressed as a valuation of the Tutte polynomial [1]. Most of these problems remain #P-hard restricted to planar graphs, see Tutte Polynomial @ Wikipedia.
[1] K. ...
9
If your statement holds, then the polynomial hierarchy collapses: $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{PH}}$ iff $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{\Sigma_k P}}$ for some fixed $k$ (by definition). But then by Toda's Theorem we have $\mathsf{PH} \subseteq \mathsf{P}^{\mathsf{\# P}} \subseteq \mathsf{P}^{\mathsf{FP}^{\mathsf{\Sigma_k P}}} =...
9
Given a set $A \subseteq B$, if you can sample uniformly from $B$, then you can estimate by repeated sampling the probability of the event that the sample is in $A$. That is, you can approximate the probability $|A| / |B|$, which is indeed close to enumerating the elements of $A$, and thus computing its size.
9
Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979). This is very clear. As for the terminology, strictly speaking, Valiant does not use the term "counting complexity" in this paper. Instead, he speaks of "counting problems" in several places. In any case, it is ...
9
As someone with a long time interest in this complexity class, I don't believe there has been any significant work on $\#P_1$ since. (I was a Ph.D. student of Mitsu Ogihara, the second author of the paper you cite, and actually raised - in informal discussions with Mitsu - the open question you cite; of course, all the actual results on this problem are due ...
9
To Question 1: The graphs induced by such edge sets are known as pseudoforests. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph induced by the edge set allows an edge orientation in which each vertex has out-degree at most 1. A graph is a pseudoforest if each connected component is a ...
8
Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question.
Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)
Only top voted, non community-wiki answers of a minimum length are eligible
