1

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<d<p$, is 'Is $\mathsf{Perm}(M)\bmod p\in\{c,\dots,d\}$?' $\mathsf{PP}$-complete?

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

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

Turbo
  • 12,812
  • 1
  • 19
  • 68

1 Answers1

5

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$.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • 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 Oct 25 '16 at 16:10
  • 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. – Emil Jeřábek Oct 25 '16 at 16:18
  • 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 Oct 25 '16 at 16:24
  • 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). ... – Emil Jeřábek Oct 25 '16 at 16:53
  • 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.) – Emil Jeřábek Oct 25 '16 at 16:59
  • 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. – Emil Jeřábek Oct 25 '16 at 17:08