# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

210 questions
Filter by
Sorted by
Tagged with
245 views

### Number of subsets on a set with partial order

Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-...
540 views

### Karp-like reductions vs Cook-like reductions for Functional Complexity Classes.

Assume we have two counting (functional) complexity classes $A$ and $B$. Suppose that Under Karp-like reductions $A$ is strictly inside $B$. Under Cook-like reductions $P^A=P^B$. What does this ...
814 views

### Permanent is #P Complete

Just to clarify, Valiant's proof does the following: Given $\phi$ a #3SAT instance with m clauses and n vars, Valiant constructs a matrix whose permanent is $4^{3m}\#\phi$. Now, this is NOT a ...
863 views

### FPRAS for #P-complete problems

I just found the following sentence from the #P wiki page: "Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if ...
506 views

### Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

Question Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? ...
259 views

### A decision problem related to the problem of counting Hamiltonian cycles

Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of ...
682 views

### How can I show a Gap-P problem is outside #P

There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take ...
1k views

### Computational complexity of random sampling

I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a ...
240 views

### Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
702 views

### Solving $n$-SAT and #$n$-SAT

Let $F$ be an $n$–SAT formula on $n$ variables (ie a CNF formula containing exclusively total clauses, with all variables in each), and let $c$ be the number of different clauses in $F$ ($c \le 2^n$). ...
463 views

### What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? ...
622 views

### Parity-L vs. NL

Parity-L, also known as $\oplus$L, is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths. A ...
410 views

### Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover

In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound ...
985 views

### How hard is it to count the number of factors of an integer?

Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$? If we knew the prime factorization of $N$, then this would ...
325 views

### What do we know about the phase transition of #P-Complete problems?

What is known about the phase transition in #P-Complete problems? Specifically, does there exists a different phase transition for #DNF-k-SAT and #CNF-k-SAT? Update: As we know, there is a phase ...
310 views

### Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?

Sorry for not-precise question. :-( There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of ...
534 views

### Is counting maximal cliques in an incomparability graph #P-complete?

This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (...
2k views

### How many DFAs accept two given strings?

Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected,...
1k views

### Survey on #P and/or counting problems

Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.
471 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
2k views

### Surprising algorithms for counting problems

There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples ...
307 views

### Complexity of counting when there is no parsimonious reduction

Let $\#A$ be a counting problem in $FP$ and let $\#B$ a counting problem with unknown complexity. Suppose there is a polynomial-time, one-to-many reduction from $B$ to $A$, but there is no specific ...
297 views

### How hard is counting the number of vertex covers after a small perturbation?

Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely,...
566 views

813 views

### Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
623 views

### The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
603 views

### The complexity of checking whether two CNF have the same number of solutions

Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No". It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of ...
823 views

### Examples of hardness phase transitions

Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$. One example is counting spin ...
Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...