3
$\begingroup$

Computing the permanent $\bmod p$ of an $n\times n$ $0/1$-matrix is $\#P$-complete if $p$ is a prime $p>n$. We have an FPTAS for approximating the $0/1$ integer matrix permanent over the reals. Moreover we can compute the permanent of an $n\times n$ $0/1$-matrix in polynomial time if its value is bounded by $n^c$ for a fixed $c>0$.

Is it possible to compute the permanent $\bmod p$ of a $0/1$ $n\times n$ integer matrix in polynomial time if its value is bounded by $(\log p)^c$ for a fixed $c>0$, where $p>n$ holds.

$\endgroup$
  • 3
    $\begingroup$ No. For fixed odd prime $p$ (e.g., $p=3$), 0–1 permanent modulo $p$ is $\mathrm{Mod}_p\mathrm{P}$-hard, and its trivially bounded by a constant. $\endgroup$ – Emil Jeřábek supports Monica May 29 '16 at 12:44
  • $\begingroup$ @EmilJeřábek $p>n$. $\endgroup$ – user34945 May 29 '16 at 18:26
  • $\begingroup$ @EmilJeřábek Ir could be easier for large primes if residue is small while the precise asymptotics makes it unclear at constant sized prime numbers. $\endgroup$ – user34945 May 30 '16 at 8:45

Your Answer

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