Questions tagged [counting-complexity]
How hard is counting the number of solutions?
252
questions
0
votes
0
answers
32
views
Power of unique counting class
One question that recently encountered is the following, suppose I have a task $L$ which has input length $n$, the problem is in the $\text{NP}$ and I promise that there is a unique solution. (The ...
0
votes
1
answer
85
views
On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)
Introduction
I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \...
- 173
0
votes
0
answers
107
views
Approximate inclusion-Exclusion?
I am trying to understand or find literature on the following problem of approximate inclusion exclusion.
Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
- 704
1
vote
2
answers
93
views
Growth rate of Knapsack Solutions
Let's say I have a Knapsack with capacity $\tau$, and I have an infinite sequence of items with weights $(a_n)_{n=1}^{\infty}$. A feasible Knapsack solution is a subset $S \subset \mathbb{N}$ such ...
- 607
0
votes
0
answers
39
views
Reducing computing the partition function to computing the number of min-cardinality (s, t) cut
Consider a partition function for a graph as follows:
\begin{equation}
\mathrm{Z}_\mathrm{G}(\beta) = \sum_{z \in \{-1, 1\}^{n}} \beta^{\underset{(i, j) \in E, i < j}{\sum} w_{i,j} ~z_i z_j},
\end{...
- 153
4
votes
0
answers
76
views
Reducing counting minimal vertex covers to counting minimum cardinality vertex covers
Consider two problems.
Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$.
Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
- 153
1
vote
0
answers
171
views
$\#NAE2SAT$ and $\oplus NAE2SAT$ complexity
Deciding $2SAT$ is in $NL$ and $\#2SAT$ is $\#P$ complete while $\oplus2SAT$ is $\oplus P$ complete.
Deciding $SAT$-$2$-$NAE$ - every clause has exactly $2$ literals, is there an $NAE$ satisfying ...
- 12.5k
0
votes
0
answers
66
views
Complexity of projected model counting
Counting the models of propositional quantifier-free formulas, #SAT, is #P-complete (under parsimonious reductions).
I was wondering about the complexity of counting the models of existentially ...
- 1,112
6
votes
1
answer
195
views
What is known about $\mathrm{NP}^{\mathrm{PP}[1]}$?
Following early discussion on Complexity of maximizing the number of models in a parametric formula it seems that the problem discussed is equivalent to a complete problem in $\mathrm{NP}^{\mathrm{PP}[...
- 1,112
6
votes
1
answer
136
views
Complexity of maximizing the number of models in a parametric formula
Let $F(x,y)$ be a propositional formula where $x$ and $y$ are vectors of Booleans. We want to maximize over $x$ the number of models of $F$ over $y$. As a decision problem, this becomes: given $F(x,y)$...
- 1,112
5
votes
0
answers
118
views
Hashing-based vs almost uniform sampling-based approximate counting
Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:
For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
- 748
10
votes
0
answers
132
views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
- 464
5
votes
0
answers
237
views
$\#$P hardness of computing weighted sum of degree $2$ polynomials
Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...
- 153
2
votes
1
answer
72
views
Relative error estimation of a special type of GapP function
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
- 153
1
vote
0
answers
101
views
Complexity of counting 3-colourings of planar bounded degree graphs
The following are known:
It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
For all $d\geq 3$, it is #P-complete to count the number ...
- 1,623
5
votes
0
answers
64
views
The complexity of tensor formula evaluation problem over an infinite field
In the paper The complexity of tensor calculus by C. Damm, M. Holzer and P. McKenzie (link), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor ...
- 81
1
vote
0
answers
78
views
Additive error approximations of GapP functions
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a ...
- 153
3
votes
0
answers
161
views
Improving the approximation in Stockmeyer's counting theorem
Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that
\begin{equation}
\left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
- 153
0
votes
0
answers
209
views
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
- 12.5k
8
votes
2
answers
243
views
Are there analogous works to PPSZ algorithm for #P?
The PPSZ algorithm tells us that we can do SAT-solving for
$k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$.
My question is that do we know such results for counting problems in class #P too ? ...
- 704
0
votes
2
answers
139
views
Knowing if there are two solutions to the subset sum problem
I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ...
- 119
3
votes
0
answers
53
views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
0
votes
0
answers
86
views
Approximate counting with non-uniform sampler
Suppose we have a predicate $\phi:\{0,1\}^n\to \{0, 1\}$ corresponding to a self-reducible problem and a FPAUS that can approximately sample from a distribution $p$ such that $\|p-u\|_{L_1}\leq \delta$...
- 101
1
vote
0
answers
104
views
How does complexity of a counting problem influence wether it admits a closed form formula or not?
In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in ...
- 704
1
vote
0
answers
138
views
Is there an oracle that separates $PH$ from counting classes?
Is there an oracle $A$ for which $P^A =PH^A \neq CH^A = NEXP^A$ holds?
- 12.5k
13
votes
1
answer
375
views
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
- 464
1
vote
1
answer
102
views
Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments
Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:
The size of $\psi$ is ...
- 6,625
4
votes
0
answers
178
views
On solving Planar Circuit SAT
This enquiry is three-sided.
Side 1 - State of the art
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
- 6,625
1
vote
0
answers
226
views
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
- 6,625
6
votes
0
answers
114
views
Counting on grid graphs
Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs?
Since there seem to be ...
- 748
2
votes
0
answers
53
views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
- 6,625
1
vote
2
answers
174
views
Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?
This question has inspired the following two questions.
Given a first order logic language, with only unary predicates, finite number of variables, $\forall$ and $\exists$ i.e no equality and ...
- 704
-2
votes
1
answer
175
views
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different.
What evidences are there that $PP$ is in $BQP$?
What evidences are there that $PP$ is not ...
- 12.5k
1
vote
0
answers
100
views
Constructing FOL formula for which counting is easy?
Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists ...
- 704
-4
votes
1
answer
156
views
does within the "range a and b" include a and b?
I have not found the answer to this doubt of mine elsewhere, hence posting it here.
It may be a silly question but I just want to be sure :P
would be great if someone could help me out with this ...
- 101
1
vote
2
answers
141
views
Asymptotic Approximation to Number of Knapsack Solutions
Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint?
More precisely, imagine I have a large number $n$ of items with bounded weights $X_1,...,X_n ...
- 607
3
votes
1
answer
90
views
Phase transition in counting feasible solutions to knapsack problems?
Imagine that you have a normalized knapsack constraint with $n$ items and weights
$w_1,...,w_n$ satisfying $\sum_{i=1}^n w_i = 1$. I'm trying to understand the behavior of the function
$$Z(c) = \#| S ...
- 607
6
votes
1
answer
225
views
Uniformly sampling or counting connected graph partitions with any number of blocks
Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard?
To clarify: By a ...
- 1,429
1
vote
0
answers
126
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 ...
- 11
0
votes
1
answer
178
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-...
- 1,623
5
votes
1
answer
205
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 ...
- 1,197
10
votes
0
answers
155
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 ...
- 1,429
0
votes
0
answers
132
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 ...
- 11
3
votes
0
answers
134
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}$,...
- 31
0
votes
0
answers
44
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 ...
- 507
5
votes
1
answer
164
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 $...
- 1,197
0
votes
1
answer
246
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 ...
- 12.5k
1
vote
1
answer
326
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?...
- 748
5
votes
0
answers
193
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 ...
- 1,197
20
votes
1
answer
486
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 ...
- 720