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 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 ?

  • 2
    $\begingroup$ I think you mean Valiant, not Vazirani. $\endgroup$ Commented Jan 7, 2014 at 17:06
  • 3
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Commented Jan 7, 2014 at 19:20
  • $\begingroup$ ${\bf \#P}$ complete under Turing reductions. $\endgroup$
    – Tayfun Pay
    Commented Jan 7, 2014 at 21:15
  • $\begingroup$ @TayfunPay Could you kindly tell me why ? A citation would be great. $\endgroup$ Commented Jan 7, 2014 at 22:39
  • $\begingroup$ This one might be a related question: cstheory.stackexchange.com/questions/20510/… $\endgroup$ Commented Jan 9, 2014 at 14:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.