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$ – Michael Lampis Jan 7 '14 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 Jan 7 '14 at 19:20
  • $\begingroup$ ${\bf \#P}$ complete under Turing reductions. $\endgroup$ – Tayfun Pay Jan 7 '14 at 21:15
  • $\begingroup$ @TayfunPay Could you kindly tell me why ? A citation would be great. $\endgroup$ – Pavithran Iyer Jan 7 '14 at 22:39
  • $\begingroup$ This one might be a related question: cstheory.stackexchange.com/questions/20510/… $\endgroup$ – Pavithran Iyer Jan 9 '14 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.