How hard is counting the number of solutions?

learn more… | top users | synonyms

0
votes
1answer
69 views

Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $. I wonder the following ...
-2
votes
0answers
24 views

How to describe the exponential nature of adding complexity [on hold]

Is there a computer science term that describes adding complexity to an IT system? For example, adding an application to an organization isn't N+1 it's exponential in the possible interactions it ...
5
votes
2answers
116 views

Is there an oracle separating Parity-P from PSPACE?

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
9
votes
1answer
123 views

Complexity of counting graph endomorphisms

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An ...
7
votes
1answer
104 views

Complexity of counting poset automorphisms

A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...
8
votes
2answers
158 views

Approximating #P-hard problems

Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
0
votes
0answers
77 views

Is there a useful notion of pathwidth-treewidth for posets?

Consider a poset $P = (V,A)$. We may define a path structuring of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where : (i) for every $x \in V$, the set $\{ i \in ...
3
votes
0answers
127 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
0
votes
0answers
39 views

Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page ...
3
votes
0answers
131 views

Counting problems with two-polymatroids

Let $S$ be a finite set. Following Lovasz (Matroid matching and some applications), let us define a polymatroid function over $S$ as a function $f : 2^S \rightarrow \mathbb{N}$ such that (1) ...
9
votes
1answer
107 views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
5
votes
1answer
186 views

Solve multiple instances of SAT with a 2-approximating #SAT query

Assume we have some oracle $A$ such that when given as input a Boolean formula $\phi$, it outputs a 2-approximation to the number of satisfying assignments of $\phi$. If we are given multiple SAT ...
4
votes
0answers
78 views

Variant of Toda's theorem for intermediate levels of the polynomial hierarchy

Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states: Let $\# wSAT$ be the number of ...
3
votes
0answers
83 views

Gradual increase in hardness from P to PH of #SAT

We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem. However, counting the number of solutions to ...
2
votes
0answers
57 views

Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...
3
votes
0answers
79 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
3
votes
0answers
101 views

Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$. We know that the problem is ...
9
votes
3answers
861 views

Counting the Number of Simple Paths in Undirected Graph

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths. Recall that a simple path is a path with no ...
4
votes
1answer
345 views

Do we know whether P^#P = NP^#P?

I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP). Recently, I have read in a journal article that ...
5
votes
0answers
89 views

Relativization of Toda's Theorem

I'm trying to figure out some consequences of the fact that Toda's Theorem relativizes. The (un-relativized) Toda's theorem states that $PH \subset P^{\#P}$ so that for any constant $k$ and any ...
4
votes
0answers
136 views

The weakly NP-complete problems and their associated counting problem

Are there weakly NP-complete problems whose associated counting problem can be computed in pseudo-polynomial time? And if one were to be found (and assuming it is #P-complete), what would be the ...
7
votes
1answer
495 views

Linear diophantine equation in non-negative integers

There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative ...
0
votes
1answer
48 views

Lower bounds on counting functions

I have a question about counting problems on arbitrary (not necessarily polynomial time) functions. Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs ...
5
votes
0answers
162 views

Weight enumerator of a binary linear code

The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as $$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$ where $$WE_{i}(\mathcal{C}) = ...
10
votes
2answers
220 views

How hard is it to count the number of local optima for a problem in PLS?

For a polynomial local search problem, we know that at least one solution (local optimum) must exist. However, many more solutions could exist, how hard is it to count the number of solutions for a ...
16
votes
0answers
296 views

Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
2
votes
0answers
160 views

What NP-complete problems are expected not to have #P-hard counting problems? [duplicate]

Let $R(v_{\bullet}, w_{\bullet})$ be some $P$-time computable relation between two binary strings $v_{\bullet}$ and $w_{\bullet}$. $NP$ problems are problems of the form: Given $v_{\bullet}$, ...
3
votes
1answer
124 views

Complexity class for Optimization problems over #P functions

Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e: $$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$ where $f\in\# ...
5
votes
0answers
141 views

How hard is counting vertex covers / edge covers on the following graph class?

Let $G=(V,E)$ be a graph having all the following restrictions: Every vertex $v \in V$ has degree $4$. Every vertex $v \in V$ belongs to at least $2$ triangles. For every vertex $v \in V$, if $v$ ...
2
votes
1answer
98 views

Intermediate Problems between FP and #P

Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I ...
4
votes
0answers
111 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
197 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
573 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
2answers
533 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 ...
21
votes
1answer
649 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 ...
4
votes
0answers
131 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
253 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
69 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 ...
11
votes
1answer
427 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
119 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 ...
3
votes
1answer
436 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
437 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
329 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 ...
8
votes
2answers
449 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
375 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
425 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 ...
-8
votes
2answers
339 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
699 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
138 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
236 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 ...