Questions tagged [counting-complexity]

How hard is counting the number of solutions?

Filter by
Sorted by
Tagged with
4
votes
2answers
162 views

Complexity of Uniform Generation of Perfect Matchings

Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to ...
1
vote
1answer
184 views

Complexity of permanent modulo prime

Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c<d<p$, is 'Is $\...
20
votes
5answers
690 views

Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
10
votes
1answer
482 views

Status of PP-completeness of MAJ3SAT

SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions? LONGER VERSION: It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence ...
5
votes
0answers
143 views

Is this volume computation problem #P Hard?

Let $A_{n\times n}$ be a positive definite diagonal matrix with positive rational entries, and let $b$ be a positive rational. Let $R(A,b)$ be the ellipsoid $ \{\mathbf{x}\in \mathbb{R}^n : ||A\mathbf{...
6
votes
1answer
183 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 ...
11
votes
3answers
719 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 ...
8
votes
2answers
1k 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 bipartite ...
19
votes
1answer
619 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 ...
3
votes
0answers
166 views

Big picture in counting complexities

(1) Is there a relation ( conjectured relation) between $\mathsf{\#P}$ and $\mathsf{CH}$? (2) How does $\tau$ conjecture in complexity of factorial fit in the picture? Is there a good reference? $\...
12
votes
0answers
125 views

Is it #P-hard to compute the number of antichains of a distributive lattice?

An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, ...
2
votes
0answers
406 views

Complexity of counting spanning subgraphs that have cycle properties

Let $G = (V, E)$ be a connected undirected graph. I am interesting in counting the number of connected spanning subgraphs having: $\ge 1$ cycle each (but can have any number of cycles), Exactly $k \...
8
votes
1answer
244 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 ...
14
votes
1answer
404 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 ...
0
votes
0answers
144 views

Consequences of VP = VNP on randomness

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct. $\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/...
8
votes
1answer
195 views

What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

In [1] it is stated that "It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform $...
4
votes
0answers
79 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 ...
3
votes
3answers
289 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 ...
4
votes
1answer
368 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 ...
6
votes
1answer
220 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 ...
2
votes
0answers
107 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....
24
votes
0answers
707 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 ...
3
votes
1answer
161 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 ...
14
votes
2answers
243 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 ...
8
votes
0answers
139 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 ...
6
votes
1answer
222 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 ...
5
votes
2answers
394 views

Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least $...
1
vote
2answers
598 views

Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
1
vote
0answers
461 views

estimating the number of comparisons of Shell Sort

I would like to estimate the number of comparisons in ShellSort. I'm using $h_s = 2^s-1$, where $s=\left \lfloor{\log(n)}\right \rfloor, \left \lfloor{\log(n)}\right \rfloor -1, \dots, 1 $ ; I know ...
16
votes
1answer
1k views

The complexity of counting simple paths in a directed graph

Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf P}$-...
9
votes
1answer
744 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
2
votes
1answer
3k views

#P-complete problems are at least as hard as NP-complete problems

I just read 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) and one of the first ...
11
votes
0answers
293 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
7
votes
2answers
201 views

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
10
votes
1answer
625 views

Probability of generating a desired permutation by random swaps

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=...
4
votes
1answer
436 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 ...
0
votes
1answer
173 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 ...
6
votes
2answers
238 views

Is there an oracle separating Parity-P from PSPACE?

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
9
votes
1answer
183 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 ...
7
votes
1answer
271 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 ...
9
votes
2answers
333 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 ...
1
vote
0answers
93 views

Is there a useful notion of pathwidth-treewidth for posets?

Consider a poset $P = (V,A)$. We may define a path structuring of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where : (i) for every $x \in V$, the set $\{ i \in [...
4
votes
0answers
319 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
1
vote
0answers
63 views

Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page ...
3
votes
0answers
145 views

Counting problems with two-polymatroids

Let $S$ be a finite set. Following Lovasz (Matroid matching and some applications), let us define a polymatroid function over $S$ as a function $f : 2^S \rightarrow \mathbb{N}$ such that (1) $f(\...
16
votes
2answers
728 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: ...
5
votes
1answer
220 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 ...
4
votes
0answers
117 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 ...
4
votes
0answers
117 views

Gradual increase in hardness from P to PH of #SAT

We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem. However, counting the number of solutions to $3-...
2
votes
0answers
72 views

Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...