# Questions tagged [counting-complexity]

How hard is counting the number of solutions?

222 questions
Filter by
Sorted by
Tagged with
10 views

### Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
42 views

### The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
115 views

### Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

This question has inspired the following two questions. Given a first order logic language, with only unary predicates, finite number of variables, $\forall$ and $\exists$ i.e no equality and ...
64 views

### Constructing FOL formula for which counting is easy?

Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists ...
127 views

### What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
30 views

### does within the “range a and b” include a and b?

I have not found the answer to this doubt of mine elsewhere, hence posting it here. It may be a silly question but I just want to be sure :P would be great if someone could help me out with this ...
977 views

### Trees: complexity of counting the number of vertex covers

Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
82 views

144 views

### Is counting the total number of faces of a polytope $\#P$ hard?

Let $P$ be a polytope defined by $Ax = b, x \geq 0$. Question: What is the complexity of computing the total number of faces of $P$? I know counting vertices is $\# P$-complete, but this problem is ...
106 views

### Network Reliability Problem

Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
119 views

### Complete problems for FP

Let FP be the class of functions $f : \{0,1\}^* \to \mathbb{N}$ that can be computed in polynomial time. Moreover, given two functions $f : \{0,1\}^* \to \mathbb{N}$ and $g : \{0,1\}^* \to \mathbb{N}$,...
158 views

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 ...
170 views

170 views

### Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

S-T CONNECTEDNESS Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$ Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$. S-T CONNECTEDNESS problem is known to be #...
585 views

### Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
69 views

### Complexity class of approximating perfect match count

We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time. Is there any evidence these approximations could be in Nick's ...
128 views

### Counting/Enumerating Minimal Edge Covers

A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it. Questions Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
29 views

### Heuristics for exact #3COLORING close to the 3-colorability threshold

What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
133 views

### Parsimonious Reduction from Unique-3SAT to NAE-3SAT

Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem ...
153 views

### Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that: 1) It is hard ...
2k views

### Complexity of counting matchings in a bipartite graph

I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem: Input: a bipartite ...
I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of Counting the number of distinct s-t cuts in a oriented graph It says ...