# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

266 questions
Filter by
Sorted by
Tagged with
1 vote
61 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 ...
1 vote
55 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 ...
111 views

79 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 ...
123 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$ ...
99 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 ...
113 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}$, ...
91 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$ ...
107 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 ...
112 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 ...
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 ...
111 views

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)$...
190 views

### Hashing-based vs almost uniform sampling-based approximate counting

Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani  states: For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
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....