Questions tagged [counting-complexity]

How hard is counting the number of solutions?

Filter by
Sorted by
Tagged with
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 ...
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}[...
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)$...
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 ...
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 ...
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 ...
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 ...
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 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 ...
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-...
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 ...
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}$,...
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 ...
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

1
2 3 4 5 6