# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

45 questions
Filter by
Sorted by
Tagged with
3k views

729 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 ...
531 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 (...
495 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 ...
321 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 ...
619 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 ...
577 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.
876 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 ...
471 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 ...
707 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 ...
602 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 ...
977 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 ...
387 views

### A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

In the paper of Ben-Dor/Halevi  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 ...
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 ...
1k views

### The complexity of counting simple paths in a directed graph

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}$-...
483 views

### Status of PP-completeness of MAJ3SAT

SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions? LONGER VERSION: It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence ...
625 views

127 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 ...
151 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 couldn'...
462 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? ...
402 views

### What are the current best upper bounds of #P?

#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP. I'm wondering if there have been any studies ...
271 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 ...
474 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 ...
319 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) ...
308 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 ...
### What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$. We also know there are degree $3$...
### Is $P^{\#P}=(P^{\#P})^{\#P}$ ?
Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one. More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?