# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

45 questions
Filter by
Sorted by
Tagged with
1k 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 ...
3k views

802 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: ...
2k views

### Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles. What are the best known upper ...
573 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 (...
518 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 ...
329 views

### A variant of #POSITIVE-2-DNF

Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations ...
656 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 ...
667 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 \}$ ...
3k views

### More on PH in PP?

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
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 ...
2k views

### Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
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.
942 views

### Counting solutions of Monotone-2CNF formulas

A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals. Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I ...
507 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 ...
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 ...
718 views

### What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
640 views

### The complexity of checking whether two CNF have the same number of solutions

Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No". It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of ...
1k 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 ...
415 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 ...
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 ...
Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf P}$-...