# Permanents - Approximation and connection to integer factorization

Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, does that imply calculating permanent is in $P$?

We assume the maximum integer size $M$ is bound and only let $n$ grow for complexity estimates.

Actually an observation is that even if if one can calculate permanent of $n \times n$ matrix in $O(n^{k})$, then $n!$ is easy to calculate. But even then it wont bother RSA since for RSA $n ~ O(2^{256})$ and $n^k$ even for $k=1$ would be formidable. Is this correct?

Ryan Williams Answer: "the permanent is #P-complete, due to Valiant's theorem in my answer below. It is possible in principle to reduce the factorization of a 256-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension N×N where $N≤c⋅256^{c}+c$ for some hopefully small constant c. However the computation of a nice upper bound on c would probably take substantial effort. It's possible c is no more than 2 or 3."

" computing the permanent is much harder than integer factoring (to my knowledge), so I doubt someone would try to reduce factoring to permanent."

If an $\epsilon$-approximation to permanent can be found in polynomial time, then I don't think it will be not worthwhile to study such an algorithm. One can take $\epsilon$ small enough so that one has to try $O(\epsilon)$ different choices for permanents. In that case factoring should have an efficient probabilistic algorithm

• Surely your time bound must depend on the lengths of integers in the initial matrix? If they are of $M$ bits where $M >> n$, how could your running time be independent of $M$? Oct 18 '10 at 6:11
• Thank you professor. When you compare growth, I believe one can assume $M$ is fixed and let $n$ grow to get an asymptotic estimate. In that situation, $n^{2}$ operations on words sizes of $O(n^{k})$ become a good estimate. Am I correct? In that situation can one say Permanent is in $P$?
– Mr.
Oct 18 '10 at 6:27
• Concerning your new question: the permanent is #P-complete, due to Valiant's theorem in my answer below. It is possible in principle to reduce the factorization of a 256-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N \times N$ where $N \leq c \cdot 256^c + c$ for some hopefully small constant $c$. However the computation of a nice upper bound on $c$ would probably take substantial effort. It's possible $c$ is no more than $2$ or $3$. Oct 21 '10 at 2:11
• This is interesting. Are there any prior works on this?
– Mr.
Oct 21 '10 at 2:38
• Probably not -- in practice, computing the permanent is much harder than integer factoring (to my knowledge), so I doubt someone would try to reduce factoring to permanent. It is just something that "follows" from the literature. Oct 21 '10 at 3:10

In this case, we would indeed say the Permanent is in $P$. First, since addition and multiplication on $O(n^k)$ size numbers can be done in $n^k \log^{O(1)} n$ time, the $O(n^2)$ arithmetic operations would take less than $O(n^{k+3})$ time to execute. If $k$ is independent of $n$ and the numbers themselves, this is polynomial time.
Secondly, if you are computing the Permanent over the integers, then in the "hard case" you may not only assume that the integers are non-negative, but also you may assume that all integers are just $0$ and $1$! This is commonly known as Valiant's theorem. For information on how to prove this, see: