How hard is counting the number of solutions?
3
votes
0answers
55 views
Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices
Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:
Their corresponding vertex induced subgraph has an even number of edges.
...
6
votes
1answer
120 views
Number of edge induced subgraphs with given vertex parity
Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.
Questions
How hard is to compute $O$?
How hard is to compute the parity of ...
16
votes
1answer
410 views
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute ...
9
votes
1answer
370 views
Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)
Consider a Monotone 3CNF formula having both the following additional restrictions:
Every variable appears in exactly $2$ clauses.
Given any $2$ clauses, they share at most $1$ variable.
I would ...
15
votes
1answer
435 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 ...
3
votes
0answers
115 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
244 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 = ...
1
vote
1answer
57 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 ...
7
votes
1answer
211 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
94 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 ...
0
votes
1answer
214 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
418 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
225 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 ...
7
votes
2answers
424 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 ...
4
votes
1answer
292 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 \}$
...
8
votes
2answers
350 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 ...
-7
votes
2answers
255 views
Is #P in NP and coNP, simultaneously? [closed]
Is #P in NP and coNP, simultaneously? What follows is a construction that has certificates for up to and including the maximum number of solutions to k-cnfs, but has no certificate for any number ...
2
votes
1answer
369 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$, ...
1
vote
0answers
121 views
What's the complexity of Spearman's rank correlation coefficient computation?
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
6
votes
2answers
210 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
222 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 ...
21
votes
1answer
630 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$ ...
16
votes
1answer
289 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 ...
8
votes
3answers
340 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 ...
3
votes
1answer
198 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
196 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 ...
12
votes
2answers
278 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 ...
12
votes
1answer
269 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 ...
3
votes
2answers
203 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
173 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 ...
4
votes
1answer
440 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 ...
6
votes
1answer
462 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 ...
4
votes
2answers
204 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 ...
1
vote
1answer
376 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 ...
4
votes
2answers
305 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
410 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
165 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 ...
12
votes
3answers
501 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 ...
4
votes
3answers
315 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 ...
1
vote
0answers
141 views
-2
votes
1answer
556 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$).
...
8
votes
0answers
218 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? ...
12
votes
1answer
320 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
185 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 ...
27
votes
2answers
671 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 ...
8
votes
1answer
234 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 ...
0
votes
0answers
206 views
Is counting the independent sets of a comparability graph with maximum degree 3 $\mathsf{\#P}$-complete? [closed]
Here we want to count the number of independent sets of a comparability graph. For $\Delta(G)=2$, i.e. the maximum degree of a vertex in $G$ is 2, the number of independent sets can be found in linear ...
3
votes
1answer
232 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 ...
11
votes
1answer
251 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 ...
27
votes
2answers
1k 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 ...
