Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [counting-complexity]

How hard is counting the number of solutions?

-1
votes
0answers
27 views

Counting class for DP problems

What would be the corresponding counting complexity class for decision problems in $DP$? Recall that $DP:=\{\mathcal{L}_1\cap\mathcal{L}_2\mid \mathcal{L}_1\in\text{NP},\mathcal{L}_2\in\text{coNP}\}$ (...
1
vote
1answer
70 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 ...
2
votes
0answers
52 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
101 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 $\...
2
votes
0answers
91 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 ...
-4
votes
0answers
94 views

Find algorithm for statiscits problem find all solutions if exist

please i am trying find algorithm for 3 months but unsuccesful, i asked my teaches of theretics informatics but unsuccesfull too. problem. for example my Mum give me 50€ with condition -> can spend ...
2
votes
2answers
128 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
62 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
107 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
25 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
84 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
142 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
39 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
51 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
106 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
175 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
210 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
105 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
137 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
92 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
217 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
183 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
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 ...
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
172 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
95 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
172 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
124 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
649 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
149 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
174 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
133 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
185 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
179 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
105 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
150 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
664 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
364 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
139 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{...
-1
votes
0answers
319 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
171 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
698 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 ...
-1
votes
0answers
238 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
612 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
118 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
385 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 \...