<p>Thanks for clarifying your earlier question. </p>

<p>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.</p>

<p>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:</p>

<p><a href="http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix" rel="noreferrer">http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix</a> </p>

<p>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.</p>

CC BY-SA 2.5
2010-10-18T06:53:36.720Z
2010-10-18T06:53:36.720Z
Ryan Williams
<p>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$?</p>

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

<p>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?</p>

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

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

<p>How about via approximations?</p>

<p>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</p>

CC BY-SA 2.5
2010-10-18T06:11:00.253Z
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$?
Ryan Williams
CC BY-SA 2.5
2010-10-18T06:27:10.457Z
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$?
Turbo
CC BY-SA 2.5
2010-10-21T02:11:29.763Z
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$.
Ryan Williams
CC BY-SA 2.5
2010-10-21T02:38:02.543Z
This is interesting. Are there any prior works on this?
Turbo
CC BY-SA 2.5
2010-10-21T03:10:07.920Z
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.
Ryan Williams
CC BY-SA 2.5
2010-10-23T05:48:28.610Z
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 probablistic algorithm.
Turbo
<cc.complexity-theory><approximation-hardness><permanent><factoring>
Permanents - Approximation and connection to integer factorization
Turbo
# Permanents - Approximation and connection to integer factorization

(Asked by: username_0 on 2010-10-18)

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?

username_1 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

**Tags:** cc.complexity-theory, approximation-hardness, permanent, factoring

> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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$?  
> **username_1**: 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$.  
> **username_0**: This is interesting. Are there any prior works on this?  
> **username_1**: 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.  
> **username_0**: 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 probablistic algorithm.  

---

## 1 answers

### Answer by username_1 on 2010-10-18. Score: 17 | Accepted answer

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.


---

