Questions tagged [counting-complexity]

How hard is counting the number of solutions?

Filter by
Sorted by
Tagged with
33
votes
2answers
2k views

When does "X is NP-complete" imply "#X is #P-complete"?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version. Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"? Of course the existence ...
7
votes
1answer
426 views

Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph. Question Which is the ...
4
votes
1answer
283 views

How hard is to compute $\Delta_{|V|}$?

Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds: $$ |\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^...
1
vote
1answer
133 views

Is #PE (#P Easy) closed under decrement?

Given a function $f : \Sigma^* \to \mathbb{N}$, define function $f_{-1}$ as: $f_{-1}(x) = f(x) - 1$ if $f(x) > 0$, and $f_{-1}(x) = 0$ otherwise. Moreover, say that a class ${\cal C}$ of functions ...
18
votes
1answer
2k views

What are the #P-complete subfamilies of #2-SAT?

Short version. The original proof that #2-SAT is #P-complete shows, in fact, that those instances of #2-SAT which are both monotone (not involving the negations of any variables) and bipartite (the ...
3
votes
0answers
185 views

Counting reduction maintaining the length of the witness for #Knapsack

I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first ...
8
votes
1answer
847 views

Counting reduction from #SAT to #HornSAT?

Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by ...
6
votes
2answers
567 views

Counting number of solutions to a specific SAT formula

I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits ...
4
votes
1answer
523 views

Number of subgraphs with given edge parity

I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume ...
9
votes
2answers
535 views

The ODD EVEN DELTA problem

Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge ...
5
votes
1answer
700 views

Number of subgraphs with a given number of nodes

Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$. The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where $V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$ ...
12
votes
3answers
1k views

Complexity of counting paths in a graph

Given a directed graph with n nodes such that each vertex has exactly two outgoing edges, and a natural number N encoded in binary, two vertices s and t, I want to count the number of (not ...
-9
votes
2answers
635 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
4
votes
1answer
2k views

A counting subset sum problem with fixed subset size and bounded weights

I am interested in the following variant of the subset sum problem: Given a set of positive integer weights $w_1,..., w_n$, such that each $w_i$ is polynomial in $n$, and given integers $s$ and $k$, ...
2
votes
0answers
342 views

What's the complexity of Spearman's rank correlation coefficient computation? [closed]

I've been studyin' the Spearman's rank correlation coefficient. If computed for two list that have both size $N$, what's the complexity of the algorithm? $O(N)$ ? Thanks in advance.
6
votes
2answers
347 views

Oracle complexity of a problem in the Counting Hierarchy

In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more ...
9
votes
1answer
388 views

Parametrized Complexity of Counting Bicliques

In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it ...
25
votes
2answers
824 views

Computational complexity of counting induced subgraphs which admit perfect matchings

Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ ...
18
votes
1answer
528 views

What is the counting complexity of random 2-SAT?

Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated ...
12
votes
3answers
2k views

counting independent sets

What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets? Is/Are there a good reference/good references on this topic? I am interested in ...
4
votes
1answer
233 views

examples of use of permanents

It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic ...
7
votes
1answer
276 views

Bibliography needed: How many "good" solutions for Knapsack?

I am trying to find some related bibliography in the field. If, by chance, my question is easy enough though, a direct answer is more than welcome. The problem is: Given that the best possible ...
14
votes
2answers
427 views

A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is $\#P$-complete. In the later part of the paper, they show the reduction chain \begin{equation} \text{IntPerm} \propto ...
15
votes
1answer
537 views

Log-space reduction from Parity-L to CNOT circuits?

Question. In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it ...
2
votes
2answers
235 views

Finding the Length of the shortest Accepting path of a NDTM

Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT. $M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non ...
2
votes
1answer
414 views

Bloom filter for storage

I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage. The problem with the Bloom filter is that, even if we ...
5
votes
1answer
2k views

Counting the number of distinct s-t cuts in a oriented graph

I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a ...
8
votes
1answer
517 views

Conditional results implying difficulty of improving upper/lower bounds for permanent

Let $A$ be a given square matrix. Is there any evidence that beating quadratic lower bounds for $B$ such that $\text{det}(B) = \text{per}(A)$ could be hard? Is there any plausible conjecture which ...
7
votes
0answers
629 views

Complexity of Exactly $A$-SAT

Let define the "Exactly $A$-SAT" problem : Given a CNF formula $F$ and a set $A$ of positive integers, is it true that the number of models of $F$ is in $A$? What is the complexity of Exactly $A$-...
4
votes
2answers
254 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
576 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
909 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 ...
7
votes
2answers
1k 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
516 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
267 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 ...
15
votes
3answers
785 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
254 views

Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
-2
votes
1answer
963 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
559 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
708 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 ...
2
votes
1answer
496 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
1k 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
398 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
341 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
606 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 (...
29
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
563 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 ...
56
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 ...