# Tagged Questions

How hard is counting the number of solutions?

83 views

### Efficient algorithms for counting $k$-clique subgraphs

Given a graph $G$ with $n >> k$ vertices, what are the fastest algorithms known to count the number of induced subgraphs in $G$ that are $k$-cliques? Are there algorithms that can do better ...
58 views

### Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
325 views

### Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

In a read-twice opposite CNF formula each variable appears twice, once positive and once negative. I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of ...
202 views

### #P-completeness and ModkP-completeness

If $\#A$ is the counting version of some corresponding decision problem $A$, when, if ever, can we determine solely on the basis of the complexity of the underlying decision problem that $\#A$ is #P-...
313 views

### Complexity of counting matchings in a bipartite graph

I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem: Input: a ...
541 views

### Division by two of functions in #P

Let $F$ be an integer valued function such that $2F$ is in $\#P$. Does it follow that $F$ is in $\#P$? Are there reasons to believe this is unlikely to always hold? Any references I should know ...
155 views

212 views

### What's the complexity of counting odd nodes in graph?

According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are ...
234 views

### Sampling a uniformly random satisfying assignment

Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists). Clearly ...
115 views

49 views

### Can weakly parsimonious counting reductions use the input instance to compute the count?

Quick version: is there a definitive definition of weakly parsimonious counting reduction for #P? Longer version: I am doing a gadget based reduction for NPC and would like to use it for #P. The ...
226 views

### Milestones in counting complexity

I want to prepare a small presentation with some of the most important results in Counting complexity, continue with recent ones and finish with some interdisciplinary results ,probably with other ...
245 views

### #P- vs PP-Completeness

Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
197 views

### Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
67 views

### Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least 6....
508 views

### What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
128 views

### Almost uniform sampling implies approximate counting

I began studying papers about approximate counting and I keep seeing the above being quoted, without further explanation. I suppose the procedure that yields the result is very well known and that is ...
191 views

### Above #P and counting search problems

I was reading the wikipedia article about the eight queens problem. It is stated that, there is no known formula for the exact number of solutions. After some searching, I found a paper named "On the ...
89 views

### Is there a counting complexity class for succint problems?

Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving ...
135 views

### FPRAS on #P complete problems and self reducibility

I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming: Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from ...
228 views

397 views

### Example of #P-intermediate problem

The previous question Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P ...
139 views

### Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $\# \mathsf{P}$ and $PH$. He proved that $\mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}}$. I wonder the following ...
182 views

### Is there an oracle separating Parity-P from PSPACE?

Is $(\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
160 views

### Complexity of counting graph endomorphisms

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An ...
200 views

### Complexity of counting poset automorphisms

A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...
218 views

### Approximating #P-hard problems

Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
85 views

235 views

### Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
208 views

### Solve multiple instances of SAT with a 2-approximating #SAT query

Assume we have some oracle $A$ such that when given as input a Boolean formula $\phi$, it outputs a 2-approximation to the number of satisfying assignments of $\phi$. If we are given multiple SAT ...
98 views

### Variant of Toda's theorem for intermediate levels of the polynomial hierarchy

Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states: Let $\# wSAT$ be the number of ...