20 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....
Ryan Williams's user avatar
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. "...
holf's user avatar
  • 2,164
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 ...
Marzio De Biasi's user avatar
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 ...
Jeffrey Shallit's user avatar
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 ...
Tayfun Pay's user avatar
  • 2,579
14 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 ...
Neal Young's user avatar
  • 9,595
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 ...
Gamow's user avatar
  • 5,772
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 ...
ricardorr's user avatar
  • 541
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 ...
Lance Fortnow's user avatar
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 ...
usul's user avatar
  • 7,595
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.
Heng Guo's user avatar
  • 375
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 ...
Heyheyhey's user avatar
  • 184
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 ...
Gara Pruesse's user avatar
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 ...
Gabriel Istrate's user avatar
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 ...
Yota Otachi's user avatar
  • 1,731
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 ...
David Eppstein's user avatar
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 ...
M. kanté's user avatar
  • 1,046
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 ...
Standa Zivny's user avatar
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}$...
Ryan Williams's user avatar
7 votes

When does "X is NP-complete" imply "#X is #P-complete"?

Fischer, Sophie, Lane Hemaspaandra, and Leen Torenvliet. "Witness-isomorphic reductions and local search." LECTURE NOTES IN PURE AND APPLIED MATHEMATICS (1997): 207-224. At the beginning of section 3....
Tayfun Pay's user avatar
  • 2,579
7 votes
Accepted

Does $NP=PP$ collapse the counting hierarchy?

We have $$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$ thus by the assumption, $$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$ as under the assumption, NP ...
Emil Jeřábek's user avatar
7 votes

$⊕P$-completeness of $⊕2SAT$

The $\oplus P$-completeness of $\oplus$2SAT was resolved much earlier than Faben's preprint in 2008: it was resolved by Valiant himself in 2006. See Leslie G. Valiant: Accidental Algorithms. FOCS ...
Ryan Williams's user avatar
7 votes

Are there analogous works to PPSZ algorithm for #P?

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets $2^{n(1-1/O(k))}$ time (like PPSZ): https://cseweb.ucsd.edu/~paturi/myPapers/pubs/...
Ryan Williams's user avatar
6 votes

What are the #P-complete subfamilies of #2-SAT?

Despite being 11 years late I hope I can still claim the bonus points! There is an (IMHO) simple and direct reduction from #SAT to #BIPARTITE-2SAT that does not rely on monotone instances. This ...
Tuomas Laakkonen's user avatar
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 ...
holf's user avatar
  • 2,164
6 votes
Accepted

How to benchmark #2-SAT counting algorithms?

I am not aware of any collections of 2CNF benchmark instances. However, one practical way of constructing #2-SAT instances that are provably hard for state-of-the-art model counters is as follows: ...
smengel's user avatar
  • 156
6 votes
Accepted

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

There is no such problem. If it's hard to sample, it's hard to integrate. Here is a sketch of the reason why. Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$. If you can integrate ...
D.W.'s user avatar
  • 11.7k
6 votes
Accepted

Count satisfying assignments of CNF formulas over all possible negation assignments

The quantity $\sum_k|\phi_k|$ can be computed in polynomial time, in fact, in uniform $\mathrm{TC}^0$. By double counting, we have $$\sum_k|\phi_k|=|\{(a,k):a\models\phi_k\}|=\sum_{a\in\{0,1\}^n}|\{k:...
Emil Jeřábek's user avatar
6 votes

What is known about $\mathrm{NP}^{\mathrm{PP}[1]}$?

Theorem 4.1 (ii) in J. Torán, Complexity Classes defined by Counting Quantifiers: $\exists \mathsf{PP} = \mathsf{NP}^{\mathsf{\# P}}$ (and thus $= \mathsf{NP}^{\mathsf{PP}[1]}$). I also have a short, ...
David Monniaux's user avatar

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