1
$\begingroup$

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)$?

Improve this question
$\endgroup$

0

Reset to default

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.