How hard is counting the number of solutions?
5
votes
1answer
129 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
37 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
50 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
101 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 ...
4
votes
0answers
161 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
184 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
102 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
133 views
0
votes
0answers
41 views
Does Ladner's theorem work in $\oplus P$ and $PP$ setting?
The answer here (Generalized Ladner's Theorem) says for many natural settings Ladner's theorem applies.
For many interesting problems such as those equivalent to finding parity of number of ...
2
votes
1answer
131 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
86 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 ...
0
votes
0answers
19 views
On $PP$, $MP$ and $\oplus P$ classes?
In here $PP^{\oplus P}\subseteq MP$ is shown and it is left as an open problem on whether $MP=PP^{\oplus P}$.
$MP\subseteq P/poly$ collapses the polynomial hierarchy and $PH\subseteq P/poly^{\oplus P}...
8
votes
1answer
211 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
175 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
106 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
111 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
80 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
168 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
91 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
162 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
118 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
549 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, ...
4
votes
0answers
141 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 ...
4
votes
1answer
161 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 ...
5
votes
1answer
128 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. #...
9
votes
1answer
180 views
Was counting complexity first introduced by Valiant in 1979?
Was #P first introduced in [1]?
[1] Valiant, Leslie G. "The complexity of computing the permanent."
Theoretical computer science 8.2 (1979): 189-201.
6
votes
1answer
158 views
What's the relationship between ASP-complete and #P-complete?
Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-...
5
votes
1answer
103 views
Counting subsets of given set with certain properties
Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$.
Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$,
such that when the $s_i$ are ...
5
votes
2answers
142 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
180 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 $\...
21
votes
5answers
653 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
299 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
134 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{...
0
votes
0answers
283 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 ...
6
votes
1answer
156 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 ...
13
votes
3answers
686 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 ...
0
votes
0answers
229 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-...
9
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
604 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?
$\...
11
votes
0answers
114 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
361 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
237 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 ...
12
votes
1answer
297 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
136 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
193 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
67 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
260 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
341 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
214 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 ...
