1. We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current best algorithm outside $NL$?

  2. Suppose deciding if permanent of $\{0,1\}$ matrices is greater than $r\in\Bbb R$ has a $BPP$ algorithm which uses only logarithmic space then is there a name for the complexity class of such a situation? Clearly it cannot be $BPP\cap L$ since $BPP\cap L=L$ would mean $PP=L$ ands the algorithm is deterministic which it clearly is not?

  • 7
    $\begingroup$ Already for $t=1$, computing the permanent mod 2 is the same as computing the determinant mod 2, which is $\oplus L$-complete, which means it is not known to be in NL. $\endgroup$ May 8, 2017 at 12:04
  • $\begingroup$ @EmilJeřábek Thank you and is it $\oplus L$-complete for $t>1$ as well? $\endgroup$
    – Turbo
    May 8, 2017 at 12:21
  • 3
    $\begingroup$ I think with Emil's observation and the result of Braverman, Kukarni and Roy computing Permanent mod $2^t$ for fixed $t$ is $\oplus L$-complete. See pdfs.semanticscholar.org/07ad/… $\endgroup$
    – Nikhil
    May 8, 2017 at 13:20
  • 3
    $\begingroup$ en.wikipedia.org/wiki/BPL_%28complexity%29 $\endgroup$ May 8, 2017 at 15:18


Your Answer

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