Questions tagged [counting-complexity]
How hard is counting the number of solutions?
213
questions
1
vote
0answers
98 views
Average case hardness of #SAT
Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.
We know that in the worst case, it is #P-complete, but what can we say about an average ...
0
votes
1answer
90 views
Is the counting version of 1-in-3 Sat #P-complete?
In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.
Cubic Planar Positive 1-in-...
5
votes
1answer
177 views
Is this a known problem, and is it #P-complete?
Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges ...
10
votes
0answers
139 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 ...
0
votes
0answers
102 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 ...
3
votes
0answers
113 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}$,...
0
votes
0answers
41 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 ...
5
votes
1answer
155 views
Counting avoiding improper 3-colorings
Given a graph $G=(V,E)$, what I call an improper $3$-coloring of $G$ is simply a function $c:V \to \{1,2,3\}$. I say that $c$ is $1$-$2$-avoiding when
there do not exist two adjacent nodes $u,v$ with $...
0
votes
1answer
165 views
Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?
If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...
1
vote
1answer
144 views
Count satisfying assignments of CNF formulas over all possible negation assignments
Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?...
5
votes
0answers
96 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 ...
20
votes
1answer
448 views
Is prime-counting function #P-complete?
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
7
votes
1answer
187 views
Holant problems and holographic reduction: simple graphs or multigraphs?
From what I can understand, Holographic reductions for Holant problems are used to show #P-hardness or polynomial time computability of certain counting problems on undirected graphs that have very ...
4
votes
2answers
328 views
A variant of #POSITIVE-2-DNF
Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations ...
0
votes
0answers
79 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 ...
4
votes
3answers
310 views
Is counting simple cycles in $P$ for graphs of bounded tree width?
Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ...
15
votes
1answer
629 views
Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?
I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ .
Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
3
votes
1answer
119 views
Complexity of #PP2DNF where we also count on the number of clauses
The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \...
1
vote
0answers
76 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....
3
votes
1answer
107 views
Computational hardness for sampling a uniform matching
A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
3
votes
0answers
74 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 ...
5
votes
2answers
134 views
Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?
The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf
Valiant proves that there exists a $\...
4
votes
1answer
192 views
Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?
I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032
1) "A further problem that can be shown ...
2
votes
2answers
163 views
Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?
S-T CONNECTEDNESS
Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$
Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$.
S-T CONNECTEDNESS problem is known to be #...
1
vote
0answers
69 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 ...
5
votes
1answer
121 views
Counting/Enumerating Minimal Edge Covers
A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.
Questions
Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
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?
5
votes
0answers
114 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
1answer
151 views
Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)
I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:
1) It is hard ...
1
vote
0answers
67 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. ...
0
votes
1answer
60 views
What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?
I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of
Counting the number of distinct s-t cuts in a oriented graph
It says ...
-1
votes
1answer
110 views
Special cases of hard counting problems that are easy
We know that bipartite planar perfect matching count is easy, permanent mod $3^t$ is easy for orthogonal matrices, permanent mod $2$ is easy, bounded rank permanent is easy.
Outside of permanent ...
5
votes
0answers
197 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 ...
4
votes
1answer
435 views
What is the complexity of counting parse trees?
A Counting Problem
Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?
An Example Instance
Let's consider an example instance consisting of a CFG $G$ with ...
0
votes
0answers
170 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 $...
2
votes
1answer
152 views
$⊕P$-completeness of$⊕2SAT$
Is $⊕2SAT$ - the parity of the number of solutions of $2$-$CNF$ formulae $\oplus P$ complete?
This is listed as an open problem in Valiant's 2005 paper https://link.springer.com/content/pdf/10.1007%...
0
votes
1answer
131 views
On polytope lattice points
Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.
Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
8
votes
1answer
239 views
Does $NP=PP$ collapse the counting hierarchy?
Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is
Theorem If $NP=PP$ then $PH^{PP}=NP$.
Proof $PP$ is closed ...
7
votes
1answer
198 views
How to benchmark #2-SAT counting algorithms?
Are there any libraries of #2-SAT instances that are hard to solve with state-of-the-art exact solvers (sharpSAT, cachet, ...)?
Alternatively: are there practical ways to generate hard #2-SAT ...
2
votes
0answers
108 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 ...
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 ...
0
votes
0answers
83 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}$ ...
2
votes
1answer
195 views
What does $\#P\subseteq FP^{PPAD}$ imply?
We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment).
Can $\#P\subseteq {PPAD}...
0
votes
1answer
119 views
What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$.
We also know there are degree $3$...
7
votes
1answer
185 views
Composition of $FP$ and $\#P$ functions
Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$.
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$.
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(...
0
votes
1answer
184 views
#P-complete with decision P
We know that an NP complete problem with a parsimonious reduction but a many one reduction is candidate problem for NP complete problem not being #P hard.
Likewise is there a possible classification ...
13
votes
2answers
802 views
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
We know the problem of counting the number of satisfying assignment in a given general boolean formula (CNF-SAT), a given DNF formula, or even a given 2SAT formula is a #P-complete problem.
Now, ...
5
votes
0answers
166 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 ...
3
votes
1answer
209 views
Where is the counting hierarchy if polynomial hierarchy collapses?
Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses.
Does the counting hierarchy collapse as well?
Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of ...
4
votes
1answer
181 views
Is #CYCLE #P-complete?
We know that #SAT is #P-complete. We also know that problems with polynomial decision versions like PERMANENT are #P-complete. Is it true that finding the number of simple cycles in a graph, i.e. #...
