Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [counting-complexity]

How hard is counting the number of solutions?

Filter by
Sorted by
Tagged with
0 votes
0 answers
55 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
BeniBela's user avatar
  • 101
2 votes
0 answers
53 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 $...
Germ's user avatar
  • 191
4 votes
0 answers
91 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 ...
Germ's user avatar
  • 191
7 votes
2 answers
309 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 ...
Daniel García's user avatar
3 votes
1 answer
75 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....
Naysh's user avatar
  • 686
1 vote
0 answers
72 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 ...
Matt Samuel's user avatar
2 votes
0 answers
82 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, ...
space_kale's user avatar
6 votes
0 answers
172 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-...
Noel Arteche's user avatar
2 votes
0 answers
79 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 ...
Habri's user avatar
  • 21
1 vote
1 answer
64 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 ...
Soham Chatterjee's user avatar
3 votes
0 answers
120 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,...
Clay Thomas's user avatar
5 votes
0 answers
132 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 ...
Michael Lampis's user avatar
3 votes
0 answers
84 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 ...
a3nm's user avatar
  • 9,449
9 votes
1 answer
303 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 ...
Igor Pak's user avatar
  • 812
0 votes
1 answer
127 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 ...
Anuj's user avatar
  • 13
2 votes
1 answer
131 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 ...
Turbo's user avatar
  • 12.9k
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 ...
Omid Yaghoubi's user avatar
3 votes
1 answer
143 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$ ...
user3508551's user avatar
  • 1,153
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 ...
Glycerius's user avatar
  • 131
7 votes
0 answers
115 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}$, ...
Rémi's user avatar
  • 262
0 votes
1 answer
110 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$ ...
SagarM's user avatar
  • 716
2 votes
0 answers
122 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 ...
AITOR GODOY's user avatar
2 votes
0 answers
116 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 ...
ddr's user avatar
  • 21
0 votes
1 answer
65 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 ...
En-Jui Kuo's user avatar
0 votes
1 answer
123 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} = \...
sebastian's user avatar
  • 173
0 votes
0 answers
129 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$ ...
SagarM's user avatar
  • 716
1 vote
2 answers
106 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 ...
Asterix's user avatar
  • 617
4 votes
0 answers
97 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 ...
AngryLion's user avatar
  • 173
1 vote
0 answers
181 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 ...
Turbo's user avatar
  • 12.9k
0 votes
0 answers
89 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 ...
David Monniaux's user avatar
6 votes
1 answer
209 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}[...
David Monniaux's user avatar
6 votes
1 answer
143 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)$...
David Monniaux's user avatar
5 votes
1 answer
215 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 ...
delete000's user avatar
  • 828
10 votes
0 answers
159 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....
Naysh's user avatar
  • 686
5 votes
0 answers
242 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 $\...
AngryLion's user avatar
  • 173
2 votes
1 answer
93 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 ...
AngryLion's user avatar
  • 173
1 vote
0 answers
122 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 ...
Cyriac Antony's user avatar
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 ...
Conn-CaoYK's user avatar
1 vote
0 answers
106 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 ...
AngryLion's user avatar
  • 173
4 votes
0 answers
341 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(...
AngryLion's user avatar
  • 173
0 votes
0 answers
223 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 ...
Turbo's user avatar
  • 12.9k
8 votes
2 answers
263 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 ? ...
SagarM's user avatar
  • 716
0 votes
2 answers
188 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 ...
user73236's user avatar
  • 119
3 votes
0 answers
58 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 ...
Colin McDonagh's user avatar
0 votes
0 answers
96 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$...
Nocturne's user avatar
  • 101
1 vote
0 answers
106 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 ...
SagarM's user avatar
  • 716
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?
Turbo's user avatar
  • 12.9k
13 votes
1 answer
925 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 ...
Naysh's user avatar
  • 686
1 vote
1 answer
128 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 ...
Giorgio Camerani's user avatar
4 votes
0 answers
215 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 ...
Giorgio Camerani's user avatar

1
2 3 4 5 6