Questions tagged [counting-complexity]

How hard is counting the number of solutions?

51 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
27
votes
0answers
622 views

The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
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 ...
24
votes
0answers
977 views

Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
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, ...
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 ...
11
votes
1answer
462 views

What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? ...
9
votes
0answers
134 views

Is counting the total number of faces of a polytope $\#P$ hard?

Let $P$ be a polytope defined by $Ax = b, x \geq 0$. Question: What is the complexity of computing the total number of faces of $P$? I know counting vertices is $\# P$-complete, but this problem is ...
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 ...
7
votes
0answers
607 views

Complexity of Exactly $A$-SAT

Let define the "Exactly $A$-SAT" problem : Given a CNF formula $F$ and a set $A$ of positive integers, is it true that the number of models of $F$ is in $A$? What is the complexity of Exactly $A$-...
5
votes
0answers
93 views

Counting matchings on 3-regular bipartite graphs

What I call a graph here allows parallel edges. Is the following problem #P-hard: INPUT: a 3-regular bipartite graph $G$ OUTPUT: the number of matchings of $G$. It is known that counting matchings ...
5
votes
0answers
106 views

Parsimonious Reduction from Unique-3SAT to NAE-3SAT

Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem ...
5
votes
0answers
193 views

How hard is APPROXIMATE-#SAT?

It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete. It is also suspected (somewhat less widely) that even deciding SAT should ...
5
votes
0answers
162 views

On space complexity of permanent modulo $2^t$?

We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current ...
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{...
5
votes
0answers
145 views

Relativization of Toda's Theorem

I'm trying to figure out some consequences of the fact that Toda's Theorem relativizes. The (un-relativized) Toda's theorem states that $PH \subset P^{\#P}$ so that for any constant $k$ and any ...
5
votes
0answers
290 views

Weight enumerator of a binary linear code

The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as $$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$ where $$WE_{i}(\mathcal{C}) = \#\{c\in\...
5
votes
0answers
180 views

How hard is counting vertex covers / edge covers on the following graph class?

Let $G=(V,E)$ be a graph having all the following restrictions: Every vertex $v \in V$ has degree $4$. Every vertex $v \in V$ belongs to at least $2$ triangles. For every vertex $v \in V$, if $v$ ...
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 ...
4
votes
0answers
321 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) ...
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-...
4
votes
0answers
233 views

The weakly NP-complete problems and their associated counting problem

Are there weakly NP-complete problems whose associated counting problem can be computed in pseudo-polynomial time? And if one were to be found (and assuming it is #P-complete), what would be the ...
4
votes
0answers
149 views

Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices

Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties: Their corresponding vertex induced subgraph has an even number of edges. ...
4
votes
0answers
273 views

What is the complexity of #satisfiable instances of k-SAT ?

To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was: Consider the 3-SAT problem on n variables. The number of possible distinct ...
4
votes
0answers
222 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
3
votes
0answers
112 views

Complete problems for FP

Let FP be the class of functions $f : \{0,1\}^* \to \mathbb{N}$ that can be computed in polynomial time. Moreover, given two functions $f : \{0,1\}^* \to \mathbb{N}$ and $g : \{0,1\}^* \to \mathbb{N}$,...
3
votes
0answers
72 views

Is #PP2DNF hard to approximate?

The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the ...
3
votes
0answers
113 views

Is Permanent $+$-reducible?

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
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? $\...
3
votes
0answers
146 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(\...
3
votes
0answers
169 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
3
votes
0answers
127 views

Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$. We know that the problem is ...
3
votes
0answers
184 views

Counting reduction maintaining the length of the witness for #Knapsack

I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first ...
3
votes
0answers
239 views

Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
2
votes
0answers
29 views

Heuristics for exact #3COLORING close to the 3-colorability threshold

What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
2
votes
0answers
107 views

On approximating problems in $\#P$

We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm $\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
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 \...
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....
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$, ...
1
vote
0answers
60 views

Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
1
vote
0answers
67 views

Complexity class of approximating perfect match count

We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time. Is there any evidence these approximations could be in Nick's ...
1
vote
0answers
59 views

Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3

By a "chain of k nodes", I mean k nodes lined up like a linked-list: o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. ...
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 ...
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 [...
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 ...
0
votes
0answers
101 views

Network Reliability Problem

Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
0
votes
0answers
40 views

Updating set of lists dependent upon a few indices

I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to ...
0
votes
0answers
77 views

Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$

For each #$k$SAT instance one can build a matrix $A$ such that $\mathrm{perm}(A) = F(\Sigma)$, where $\Sigma$ is the solution count of the $k$SAT formula and $F$ an easy to invert function. My ...
0
votes
0answers
168 views

On PP in communication complexity

Aho says $D(f)=O(N(f)N(\overline f))$ where $D(f)$ is deterministic communication complexity and $N(f)$ is non-deterministic version. Do we know $PP(f)=\Omega(2^{(N(f)N(\overline f))^{O(1)}})$ or $...
0
votes
0answers
82 views

On permanent mod $3^t$ computation

By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ ...