<p>First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied constant depending on the constant in the input bit size), we know it outright.</p>

<p>Your problem with $p$ allowed to have $O(\log n)$ bits is PP-hard under polynomial-time <em>Turing</em> reductions: in order to compute permanent, just compute it modulo every prime below $cn^2$, and use the Chinese remainder theorem to find its value modulo the product of these primes, which is roughly $e^{cn^2}$. By the above, this provides the true value of the permanent for suitable $c$.</p>

<p>There is a serious obstacle to using your problem for primes with $\omega(\log n)$ bits: any reduction to this problem must in particular produce a prime number, and we know of no provably correct deterministic way of computing large primes significantly faster than brute force.</p>

<p>But if you allow randomized reductions, or say, reductions with free access to solutions of the search problem “given $x$, find a prime $p$ such that $x\le p\le2x$”, then you can reduce the number of oracle queries in the reduction of permanent I gave above by using a smaller number of larger primes: if you allow primes $p$ with $m(n)$ bits, you can do away with about $n^2/m(n)$ oracle calls.</p>

<p>For $m(n)=n^\alpha$ with constant $\alpha$, you can use padding to reduce the number of queries to $1$, i.e., to get a randomized many-one reduction: given the input $n\times n$ matrix $M$, find a prime $p$ of at least $n^2$ bits, and let $M'$ be the matrix $M$ padded with diagonal $1$s to dimension $n'\times n'$, where $n'^\alpha\ge\log p$. Then ask for the permanent of $M'$ modulo $p$.</p>

CC BY-SA 3.0
2016-10-25T16:10:20.440Z
So for $O(\log n)$ bit it is complete while while we only have a randomized reduction with $\omega(\log n)$ primes. If I had said $p$ was just an integer may be there would have been a better chance of proving completeness with current knowhow.
Turbo
CC BY-SA 3.0
2016-10-25T16:18:52.120Z
It is still complete under Turing reductions if you allow larger primes, unless you actively disallow small primes. What I was getting at is that if you want completeness under many-one reductions rather than just Turing reductions, you *will* need large primes, and then you run into the trouble of finding them. But yes: if you allow non-prime $p$, then this difficulty disappears.
Emil Jeřábek
CC BY-SA 3.0
2016-10-25T16:24:34.570Z
When they say $PP$-complete they use Many-one reductions right? I believe then results like $PH\subseteq P^{PP}$ come from Turing reductions. Is every turing reduction hypothesised to have a manyone variant for $PP$ case? sorry for too many irrelevant queries.
Turbo
CC BY-SA 3.0
2016-10-25T16:53:39.357Z
Well, yes, many-one reductions are more common for comparison of languages and in definitions of X-completeness for various class X. The difference between Turing and many-one reductions is likely genuine in this case: in particular, I would expect you problem with $O(\log n)$-bit primes *not* to be PP-hard under many-one reductions. Also, it is somewhat likely that PP is not itself closed under Turing reductions (i.e., it is different from $\mathrm{P^{PP}}$), though it’s not very clear  (e.g., PP *is* known to be closed under *parallel* Turing reductions for nontrivial reasons). ...
Emil Jeřábek
CC BY-SA 3.0
2016-10-25T16:59:18.857Z
... I believe there was some cstheory question on that very topic. Anyway, now I noticed that I concentrated on PP-hardness in my answer, and neglected the other side of the issue: in order to be PP-complete, your problem would have to be in PP in the first place, and this is fairly unlikely (unless indeed $\mathrm{PP=P^{PP}}$; the problem is obviously in $\mathrm{P^{PP}}$). For instance, integer permanent modulo $3$ is a $\mathrm{Mod_3P}$-complete problem, and I believe $\mathrm{Mod_3P}$ is not assumed to be included in PP. (So, I shouldn’t have written “complete” in my first comment above.)
Emil Jeřábek
CC BY-SA 3.0
2016-10-25T17:08:38.930Z
Ah, the question I was thinking about was http://cstheory.stackexchange.com/questions/3278 . It doesn’t directly ask about $\mathrm{PP=P^{PP}}$, but it is quite related, and there is relevant information (or opinions) in the answers.
Emil Jeřábek
CC BY-SA 3.0
2016-10-25T10:36:30.317Z
2016-10-25T10:36:30.317Z
Emil Jeřábek
<p>Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c&lt;d&lt;p$, is 'Is $\mathsf{Perm}(M)\bmod p\in\{c,\dots,d\}$?' $\mathsf{PP}$-complete?</p>

<p>What if $p$ is $O(\log n)$ bits or even smaller?</p>

<p>Without the ${}\bmod p$ it is known to be $\mathsf{PP}$-complete.</p>

<cc.complexity-theory><complexity-classes><counting-complexity><reductions><permanent>
Complexity of permanent modulo prime
Turbo
# Complexity of permanent modulo prime

(Asked by: username_0 on 2016-10-25)

Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c

What if $p$ is $O(\log n)$ bits or even smaller?

Without the ${}\bmod p$ it is known to be $\mathsf{PP}$-complete.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, reductions, permanent


---

## 1 answers

### Answer by username_1 on 2016-10-25. Score: 5 | Accepted answer

First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied constant depending on the constant in the input bit size), we know it outright.

Your problem with $p$ allowed to have $O(\log n)$ bits is PP-hard under polynomial-time *Turing* reductions: in order to compute permanent, just compute it modulo every prime below $cn^2$, and use the Chinese remainder theorem to find its value modulo the product of these primes, which is roughly $e^{cn^2}$. By the above, this provides the true value of the permanent for suitable $c$.

There is a serious obstacle to using your problem for primes with $\omega(\log n)$ bits: any reduction to this problem must in particular produce a prime number, and we know of no provably correct deterministic way of computing large primes significantly faster than brute force.

But if you allow randomized reductions, or say, reductions with free access to solutions of the search problem “given $x$, find a prime $p$ such that $x\le p\le2x$”, then you can reduce the number of oracle queries in the reduction of permanent I gave above by using a smaller number of larger primes: if you allow primes $p$ with $m(n)$ bits, you can do away with about $n^2/m(n)$ oracle calls.

For $m(n)=n^\alpha$ with constant $\alpha$, you can use padding to reduce the number of queries to $1$, i.e., to get a randomized many-one reduction: given the input $n\times n$ matrix $M$, find a prime $p$ of at least $n^2$ bits, and let $M'$ be the matrix $M$ padded with diagonal $1$s to dimension $n'\times n'$, where $n'^\alpha\ge\log p$. Then ask for the permanent of $M'$ modulo $p$.

> **Comments:**
> **username_0**: So for $O(\log n)$ bit it is complete while while we only have a randomized reduction with $\omega(\log n)$ primes. If I had said $p$ was just an integer may be there would have been a better chance of proving completeness with current knowhow.  
> **username_1**: It is still complete under Turing reductions if you allow larger primes, unless you actively disallow small primes. What I was getting at is that if you want completeness under many-one reductions rather than just Turing reductions, you *will* need large primes, and then you run into the trouble of finding them. But yes: if you allow non-prime $p$, then this difficulty disappears.  
> **username_0**: When they say $PP$-complete they use Many-one reductions right? I believe then results like $PH\subseteq P^{PP}$ come from Turing reductions. Is every turing reduction hypothesised to have a manyone variant for $PP$ case? sorry for too many irrelevant queries.  
> **username_1**: Well, yes, many-one reductions are more common for comparison of languages and in definitions of X-completeness for various class X. The difference between Turing and many-one reductions is likely genuine in this case: in particular, I would expect you problem with $O(\log n)$-bit primes *not* to be PP-hard under many-one reductions. Also, it is somewhat likely that PP is not itself closed under Turing reductions (i.e., it is different from $\mathrm{P^{PP}}$), though it’s not very clear  (e.g., PP *is* known to be closed under *parallel* Turing reductions for nontrivial reasons). ...  
> **username_1**: ... I believe there was some cstheory question on that very topic. Anyway, now I noticed that I concentrated on PP-hardness in my answer, and neglected the other side of the issue: in order to be PP-complete, your problem would have to be in PP in the first place, and this is fairly unlikely (unless indeed $\mathrm{PP=P^{PP}}$; the problem is obviously in $\mathrm{P^{PP}}$). For instance, integer permanent modulo $3$ is a $\mathrm{Mod_3P}$-complete problem, and I believe $\mathrm{Mod_3P}$ is not assumed to be included in PP. (So, I shouldn’t have written “complete” in my first comment above.)  
> **username_1**: Ah, the question I was thinking about was http://cstheory.stackexchange.com/questions/3278 . It doesn’t directly ask about $\mathrm{PP=P^{PP}}$, but it is quite related, and there is relevant information (or opinions) in the answers.  

---

