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$?
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?
$\begingroup$
$\endgroup$
4
-
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$– Emil JeřábekMay 8, 2017 at 12:04
-
$\begingroup$ @EmilJeřábek Thank you and is it $\oplus L$-complete for $t>1$ as well? $\endgroup$– TurboMay 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$– NikhilMay 8, 2017 at 13:20
-
3$\begingroup$ en.wikipedia.org/wiki/BPL_%28complexity%29 $\endgroup$– Emil JeřábekMay 8, 2017 at 15:18
Add a comment
|