How hard is counting the number of solutions?
10
votes
0answers
115 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
352 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
429 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 ...
2
votes
0answers
109 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
243 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
56 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
200 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
91 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
207 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
412 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
199 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
411 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
282 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
347 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
247 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 ...
