# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

239 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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}^...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 \}$ ...
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 ...
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 ...
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$, ...
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.
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 \text{IntPerm} \propto ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$-...
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-...
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 ...
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 ...
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 ...
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? ...
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 ...
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 ...
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 ...
0answers
254 views

### Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
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$). ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 (...
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,...
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.
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 ...
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 ...