Questions tagged [counting-complexity]
How hard is counting the number of solutions?
250
questions
-4
votes
0
answers
20
views
How can I calculate the computational complexity of an equation composed of 2n multiplications and 2nm^2 additions? [closed]
I want to calculate the computational complexity in term of the big (O).
My equation is:
It composed of 2n multiplications and 2nm^2 additions.
The complexity of this equation is it O( 2n + 2nm^2 ) ...
- 93
1
vote
2
answers
84
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 ...
- 587
0
votes
0
answers
38
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
72
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
167
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
194
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
113
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
128
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....
- 454
5
votes
0
answers
232
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
63
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
95
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,603
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
72
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
129
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
205
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
235
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 ? ...
- 684
0
votes
2
answers
128
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
51
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
102
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 ...
- 684
1
vote
0
answers
137
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
12
votes
1
answer
342
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 ...
- 454
1
vote
1
answer
99
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,615
4
votes
0
answers
168
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,615
1
vote
0
answers
225
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,615
6
votes
0
answers
109
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
52
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,615
1
vote
2
answers
167
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 ...
- 684
-2
votes
1
answer
171
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
92
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 ...
- 684
-4
votes
1
answer
109
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
139
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 ...
- 587
3
votes
1
answer
89
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 ...
- 587
6
votes
1
answer
214
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
170
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,603
5
votes
1
answer
203
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,095
10
votes
0
answers
152
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
130
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
128
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 ...
- 497
5
votes
1
answer
163
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,095
0
votes
1
answer
243
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
310
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
182
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,095
20
votes
1
answer
477
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
7
votes
1
answer
236
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 ...
- 1,095
4
votes
2
answers
340
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 ...
- 1,095