7
$\begingroup$

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

How about via approximations?

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

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Ryan Williams Oct 18 '10 at 6:11
  • $\begingroup$ 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$? $\endgroup$ – T.... Oct 18 '10 at 6:27
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ryan Williams Oct 21 '10 at 2:11
  • $\begingroup$ This is interesting. Are there any prior works on this? $\endgroup$ – T.... Oct 21 '10 at 2:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Oct 21 '10 at 3:10
16
$\begingroup$

Thanks for clarifying your earlier question.

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:

http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix

This means that restricting to a non-negative matrix with bounded entries is not really a restriction of the Permanent problem. A polynomial time algorithm for this version of the problem would result in a polynomial time algorithm for the Permanent over any integer matrix.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.