20
votes
Accepted
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
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. "...
- 1,855
19
votes
Accepted
The complexity of counting simple paths in a directed graph
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. ...
- 22.3k
19
votes
Status of PP-completeness of MAJ3SAT
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....
- 26.3k
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,888
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.3k
15
votes
Accepted
Probability of generating a desired permutation by random swaps
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 ...
- 16.2k
15
votes
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
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 ...
- 2,579
14
votes
Accepted
Above #P and counting search problems
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 ...
- 4,584
14
votes
Example of #P-intermediate problem
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 \...
- 35.7k
13
votes
Accepted
Complexity of counting matchings in a bipartite graph
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 ...
- 5,712
13
votes
Accepted
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
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 ...
- 8,228
12
votes
Accepted
Approximating #P-hard problems
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 ...
- 2,743
11
votes
Accepted
Can we approximate the number of words accepted by an NFA?
There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
- 521
11
votes
More on PH in PP?
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 ...
- 8,546
10
votes
Accepted
Easy decision hard counting Parametrized
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 $...
- 9,378
10
votes
Accepted
What's the complexity of counting odd nodes in graph?
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 ...
- 7,052
10
votes
Accepted
$⊕P$-completeness of $⊕2SAT$
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.
- 375
9
votes
Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?
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$ ...
- 35.7k
9
votes
Accepted
Almost uniform sampling implies approximate counting
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 ...
- 9,556
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
Was counting complexity first introduced by Valiant in 1979?
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 ...
- 184
9
votes
Accepted
Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?
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 ...
- 131
9
votes
Accepted
Is this a known problem, and is it #P-complete?
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 ...
- 1,721
8
votes
Accepted
#P- vs PP-Completeness
Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for ...
- 250
8
votes
Accepted
Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?
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 ...
- 1,968
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.2k
8
votes
Accepted
Is counting simple cycles in $P$ for graphs of bounded tree width?
A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for ...
- 1,026
8
votes
Accepted
Counting avoiding improper 3-colorings
I don't know whether this problem has been studied but I think its #P-hardness should follow directly from the #CSP dichotomy established by Bulatov (Bulatov JACM'13), later simplified by Dyer and ...
- 945
Only top scored, non community-wiki answers of a minimum length are eligible