Questions tagged [counting-complexity]
How hard is counting the number of solutions?
279 questions
0
votes
0
answers
4
views
Generalization of $\mathsf{MAJSAT}$ to higher levels of the Counting Hierarchy
$\mathsf{MAJSAT}$ is known to be complete for the first level $\mathsf{C_1P = PP}$ of the Counting Hierarchy and $\mathsf{MAJMAJSAT}$ is known to be complete for the second level $\mathsf{C_2P = {PP}^...
2
votes
0
answers
92
views
Interesting counting problems with polynomially many solutions
Commonly occurring #P problems (e.g., #SAT) are often studied in the regime where instances with $n$ Boolean variables have $2^{\Theta(n)}$ solutions, in part because instances with $O(1)$ solutions ...
- 848
8
votes
3
answers
233
views
Are the notions of #P-completeness via Turing reductions and polynomial many-one counting reductions equivalent?
I am not aware of any source that compares both notions. Are there two functions in $\#P$, say $f$ and $g$, such that $f \in \mathbf{FP}^g$ but there is no polynomial-time many-one counting reduction ...
6
votes
1
answer
313
views
Polylog-space vs NP
Let $\text{polyL} = \cup_{c} \text{SPACE}[\log^c n]$ be the set of all problems that can be solved using polylog space, what is known/believed about its relation with NP? And perhaps even PP?
I'm ...
- 61
0
votes
0
answers
131
views
$P^{\#P}$ complete problems
Are there any known $P^{\#P}$ complete problems?
The problem would have to be at least as hard as anything in the polynomial hierarchy, but perhaps not as hard as PSPACE
- 101
2
votes
0
answers
68
views
Do prefix hash functions work well for approximate counting?
Given some set $S \subseteq \{0,1\}^n$, suppose we want to approximate $|S|$. One approach is hashing-based approximate counting, which exploits the structure of hash functions to approximately halve $...
- 191
2
votes
0
answers
95
views
Evidence for $\oplus P\subseteq\#P$ and barriers to proving it
Is there evidence that $\oplus P\subseteq\#P$ and evidence towards $\oplus P\not\subseteq\#P$ ? We know $\oplus P\subseteq FP^{\#P}$
What are some barriers to proving this inclusion $\oplus P\subseteq\...
- 13.3k
4
votes
0
answers
101
views
Working out the constants and probabilities of Stockmeyer's approximate counting algorithm
Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash ...
- 191
7
votes
2
answers
353
views
Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?
Consider the given problem: you have a set S of positive integers, and you want to find how many subsets have a sum of at most T. I highly suspect that the problem is hard since a polynomial time ...
- 157
3
votes
1
answer
87
views
What is the fastest algorithm for computing exact network reliability?
In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
- 696
1
vote
0
answers
78
views
Properties of #P functions that a GapP function may violate
I want to show a specific GapP problem is likely not in #P, actually very closely related to this question in terms of the area of mathematics it is from: How can I show a Gap-P problem is outside #P
...
- 111
2
votes
0
answers
89
views
Extending Karp Reductions of a Decision Problem to Cook Reductions of the Associated Counting Problem
It seems that most NP-complete decision problems have #P-complete corresponding counting problems, with many examples showing this and no known counterexamples. In Jerrums' lecture notes `Counting, ...
7
votes
0
answers
185
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 1,049
2
votes
0
answers
91
views
Crafting ${NP}^{\#P}$-complete problems
Some related posts:
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
- 21
1
vote
1
answer
73
views
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Given any matrix of univariate polynomials of degree $\leq n^{O(1)}$ then prove that the coefficent of $x^i$ in the determinant of the matrix is in $GapL$
Hint: Use Mahajan-Vinay's result of ...
- 280
3
votes
0
answers
139
views
Computational complexity of finding the $n$th Dedekind Number
Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,...
- 205
5
votes
0
answers
143
views
Do fast satisfiability algorithms imply fast algorithms for parity SAT?
$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P).
Suppose we have a ...
- 3,722
3
votes
0
answers
96
views
FPRAS to estimate the probability to get a cyclic subgraph of a directed graph
Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge ...
- 9,838
9
votes
1
answer
316
views
Complexity of permanent verification
Consider the problem of permanent verification:
$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?
Question: Is it known to be NP-hard? Should ...
- 812
0
votes
1
answer
131
views
Complexity of "opposite" version of a variant of #Positive-2-SAT
In this post ,I introduced a new variant of #Positive-2-SAT .
This version of problem puts restrictions on the inputs of the
#Positive-2-SAT such that we can only choose at max only 2 clauses from ...
- 13
2
votes
1
answer
146
views
Perm and Det mod $2^k$ - I
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 13.3k
3
votes
0
answers
80
views
Extending fagin’s theorem for #P (for arbitary structure)
While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures.
This is a corollary from fagin’s theorem. I have read fagin’s ...
- 139
3
votes
1
answer
160
views
Complexity of sampling a clique uniformly at random
Let $G$ be an undirected graph, and let $C_1, ..., C_M$ denote all possible cliques in $G$.
What is known on the complexity of sampling a clique uniformly at random. That is, returning clique $C_i$ ...
- 1,163
3
votes
0
answers
103
views
$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$
I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
- 131
7
votes
0
answers
121
views
Complexity of the unique homomorphism problem up to automorphisms
I am interested in the following problem: given two relational structures $\mathbf{A},\mathbf{B}$,
is there a unique homomorphism from $\mathbf{A}$ to $\mathbf{B}$ up to automorphisms of $\mathbf{B}$, ...
- 262
0
votes
1
answer
126
views
Number of equivalent formulas in a function-free first order logic language?
In this paper by Martin Grohe, in the first paragraph of section 4.1, it says:
"because upto logical equivalence there only exist finitely many $FO[\rho]$ formulas of quantifier rank at most $q$ ...
- 716
2
votes
0
answers
135
views
Problems in $P^{PP}$
I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
- 21
2
votes
0
answers
119
views
Question about #P-completeness and NP-completeness
In the book Nature of Computation by Moore & Mertens there is an exercise saying "show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every ...
- 21
0
votes
1
answer
66
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
133
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} = \...
- 183
0
votes
0
answers
142
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$ ...
- 716
1
vote
2
answers
110
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 ...
- 627
4
votes
0
answers
102
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 ...
- 193
1
vote
0
answers
186
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 ...
- 13.3k
0
votes
0
answers
98
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,122
6
votes
1
answer
211
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,122
6
votes
1
answer
147
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,122
5
votes
1
answer
230
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 ...
- 848
10
votes
0
answers
162
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....
- 696
5
votes
0
answers
243
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 $\...
- 193
2
votes
1
answer
96
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 ...
- 193
1
vote
0
answers
128
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,869
5
votes
0
answers
68
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
120
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 ...
- 193
5
votes
0
answers
401
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(...
- 193
0
votes
0
answers
226
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 ...
- 13.3k
8
votes
2
answers
265
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 ? ...
- 716
0
votes
2
answers
220
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
59
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
101
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