<ol>
<li><p>We know from <a href="https://cstheory.stackexchange.com/questions/37573/on-complexity-of-permanent-bmod-2t?rq=1">here</a> 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$?</p></li>
<li><p>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?</p></li>
</ol>

CC BY-SA 3.0
2017-05-08T12:04:59.270Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-05-08T12:21:49.833Z
@EmilJeřábek Thank you and is it $\oplus L$-complete for $t>1$ as well?
Turbo
CC BY-SA 3.0
2017-05-08T13:20:50.513Z
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 https://pdfs.semanticscholar.org/07ad/32184962e27296250ebb6b32d0d92383a131.pdf
Nikhil
CC BY-SA 3.0
2017-05-08T15:18:42.143Z
https://en.wikipedia.org/wiki/BPL_%28complexity%29
Emil Jeřábek
<counting-complexity><permanent><space-complexity><logspace><space-time-tradeoff>
On space complexity of permanent modulo $2^t$?
Turbo
# On space complexity of permanent modulo $2^t$?

(Asked by: username_0 on 2017-05-08)

1. We know from [here](https://cstheory.stackexchange.com/questions/37573/on-complexity-of-permanent-bmod-2t?rq=1) 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?

**Tags:** counting-complexity, permanent, space-complexity, logspace, space-time-tradeoff
> **Comments:**
> **username_1**: 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.  
> **username_0**: @EmilJeřábek Thank you and is it $\oplus L$-complete for $t>1$ as well?  
> **username_2**: 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 https://pdfs.semanticscholar.org/07ad/32184962e27296250ebb6b32d0d92383a131.pdf  
> **username_1**: https://en.wikipedia.org/wiki/BPL_%28complexity%29  

---

## 0 answers

