<p>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 <a href="http://www.sciencedirect.com/science/article/pii/0304397579900446" rel="nofollow">Valiant</a>, where $l = \Theta(n)$.</p>

<p>We know that the problem is not in $\mathsf{P}$, unless $l = \mathcal{O}(\log_2 n)$. What can we say about the complexity of the problem when $l = \mathcal{o}(n)$ as well as $\log_2 n = \mathcal{o}(l)$ ? For example, if $l = \text{polylog}(n)$ ?</p>

<p>Does the problem remain $\#\mathsf{P}$-complete ? Or is it complete for a class in some level of the polynomial hierarchy ?</p>

CC BY-SA 3.0
2014-01-07T17:06:12.717Z
I think you mean Valiant, not Vazirani.
Michael Lampis
CC BY-SA 3.0
2014-01-07T19:20:12.187Z
So your input is a polylog-sized description of a matrix plus some padding to make the input length n? If so, we can use the exponential time algorithm for the permanent to compute it in quasi-polynomial time (in n), so it's certainly not hard for NP (or any superset, such as #P) unless ETH fails.
Yonatan N
CC BY-SA 3.0
2014-01-07T21:15:29.843Z
${\bf \#P}$ complete under Turing reductions.
Tayfun Pay
CC BY-SA 3.0
2014-01-07T22:39:10.667Z
@TayfunPay Could you kindly tell me why ? A citation would be great.
Pavithran Iyer
CC BY-SA 3.0
2014-01-09T14:05:34.923Z
This one might be a related question: http://cstheory.stackexchange.com/questions/20510/variant-of-todas-theorem-for-intermediate-levels-of-the-polynomial-hierarchy
Pavithran Iyer
<complexity-classes><counting-complexity><permanent><polynomial-hierarchy>
Computing the permanent with polylog size matrices
Pavithran Iyer
# Computing the permanent with polylog size matrices

(Asked by: username_0 on 2014-01-07)

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](http://www.sciencedirect.com/science/article/pii/0304397579900446), where $l = \Theta(n)$.

We know that the problem is not in $\mathsf{P}$, unless $l = \mathcal{O}(\log\_2 n)$. What can we say about the complexity of the problem when $l = \mathcal{o}(n)$ as well as $\log\_2 n = \mathcal{o}(l)$ ? For example, if $l = \text{polylog}(n)$ ?

Does the problem remain $\#\mathsf{P}$-complete ? Or is it complete for a class in some level of the polynomial hierarchy ?

**Tags:** complexity-classes, counting-complexity, permanent, polynomial-hierarchy
> **Comments:**
> **username_1**: I think you mean Valiant, not Vazirani.  
> **username_2**: So your input is a polylog-sized description of a matrix plus some padding to make the input length n? If so, we can use the exponential time algorithm for the permanent to compute it in quasi-polynomial time (in n), so it's certainly not hard for NP (or any superset, such as #P) unless ETH fails.  
> **username_3**: ${\bf \#P}$ complete under Turing reductions.  
> **username_0**: @TayfunPay Could you kindly tell me why ? A citation would be great.  
> **username_0**: This one might be a related question: http://cstheory.stackexchange.com/questions/20510/variant-of-todas-theorem-for-intermediate-levels-of-the-polynomial-hierarchy  

---

## 0 answers

