Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log n)$ by https://mbraverm.princeton.edu/files/planarCounting.pdf.

Suppose we know permanent and determinant mod $2^{k-1}$. Then

  1. what is the best complexity class we would be in for each of permanent and determinant modulo $2^k$ when $k=\Omega(\log n)$?

  2. what is the best time complexity known when $k=\Omega(\log n)$?



Your Answer

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