Questions tagged [counting-complexity]

How hard is counting the number of solutions?

Filter by
Sorted by
Tagged with
4
votes
2answers
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-...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
6
votes
2answers
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 ...
5
votes
1answer
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? ...
3
votes
1answer
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 ...
14
votes
3answers
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 ...
6
votes
3answers
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 ...
3
votes
0answers
240 views

Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
-2
votes
1answer
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$). ...
11
votes
1answer
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? ...
13
votes
1answer
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 ...
1
vote
1answer
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 ...
30
votes
2answers
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 ...
11
votes
1answer
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 ...
3
votes
1answer
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 ...
13
votes
1answer
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 (...
28
votes
2answers
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,...
23
votes
4answers
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.
17
votes
1answer
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 ...
54
votes
3answers
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 ...
0
votes
1answer
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 ...
7
votes
2answers
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,...
13
votes
6answers
566 views

Any algorithmic problem has a time complexity dominated by counting?

What I refer to as counting is the problem that consists in finding the number of solutions to a function. More precisely, given a function $f:N\to \{0,1\}$ (not necessarily black-box), approximate $\#...
4
votes
0answers
273 views

What is the complexity of #satisfiable instances of k-SAT ?

To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was: Consider the 3-SAT problem on n variables. The number of possible distinct ...
2
votes
2answers
487 views

Examples of #P problems which are in FP ?

Is there any case of SAT problems (except the affine ones) whose counting version can be computed in polynomial time ?
6
votes
3answers
904 views

Trees: complexity of counting the number of vertex covers

Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
1
vote
1answer
325 views

Number of Vertex Covers: when it is polynomial and when it is superpolynomial

The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to ...
10
votes
1answer
306 views

Holographic Algorithms - Equivalence of Bases

I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper. I cannot see why is it the case that if there is a generator with certain values ...
14
votes
4answers
2k views

Counting the number of vertex covers: when is it hard?

Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$. I'd like to know if there is any result showing how the hardness of such problem varies with ...
13
votes
2answers
506 views

What's the complexity of Median-SAT?

Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$ represent a variable assignment and $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses ...
1
vote
1answer
231 views

Complexity of a certain leaf language with Prime & Composite number of accepting paths.

Given a non-deterministic Turing Machine that runs in polynomial time, it accepts if the number of accepting paths are composite, it rejects if the number of accepting paths are prime and it outputs I ...
7
votes
3answers
548 views

Does there exist a complexity class such that the number of accepting paths is a prime number?

#P asks the total number of accepting paths. PP asks at least half of paths be accepting. Parity-P asks the number of accepting paths be even. UP asks the number of accepting paths to be one. Are ...
6
votes
3answers
388 views

Are there any natural hard problems where it is required that the number of solutions are always more than one?

If there are no accepting paths or only one accepting path, it outputs zero. And If there are more than one accepting paths it outputs Yes. I am looking for a natural problem that requires this.
-2
votes
1answer
247 views

Complexity of counting the number of Good-perfect matching in the bipartite graph

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...
13
votes
4answers
722 views

Regarding Pfaffian Methods in Counting and Combinatorics

Recently, I was going over an introduction to Holographic Algorithms. I came across some combinatorial objects called Pfaffians. I do not really know much about those at the moment and came across ...
1
vote
1answer
349 views

The Relationship between P^NP and the Permanent

In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in ...
6
votes
2answers
313 views

Complexity of counting weighted cycles in planar graphs?

Assume G is a weighted planar graph, nodes and edges in G are weighted, and K is a given constant. A is a decision problem with following description: Does G contain a cycle with total ...
12
votes
2answers
2k views

Complexity of counting all connected subgraphs

Let G be a connected graph. What is the complexity of counting all connected subgraphs if G is of the following types? G is general. G is planar. G is bipartite. I don't care about ...
14
votes
2answers
824 views

#P-complete problem whose decision version is in P

1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P? For example, can there be a ...
63
votes
1answer
3k views

More on PH in PP?

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
37
votes
4answers
3k views

Is $PH \subseteq PP$?

We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$. Do we know whether $...
24
votes
2answers
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 ...
27
votes
0answers
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". ...
14
votes
3answers
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 ...
20
votes
4answers
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 ...
15
votes
1answer
421 views

Graph decompositions for combining “local” functions of vertex labelings

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 ...
12
votes
2answers
1k views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$. If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
1
vote
1answer
694 views

Is $P^{\#P}=(P^{\#P})^{\#P}$ ?

Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one. More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?
15
votes
3answers
2k views

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles. What are the best known upper ...