2
$\begingroup$

There was a comment here that " 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\cdot256^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."

Is it possible to convert factoring integers to calculating permanent? That is given $\log N$ bit integer to factor, how can one reduce factoring such an integer to calculating permanent of $(\log n)^c\times(\log n)^c$ matrix for a fixed $c$?


I also ask if computing $a(a+1)(a+2)\dots(a+n)$ with $a\in\Bbb N$ is also easy (done in $\log^cn$ steps if permanent of $N\times N$ matrix is easy (done in $N^c$ steps). Note that at $a=1$ we have $n!$, and permanent of all $1$ matrix needs $n\times n$ size and hence needs $n^c$ time even if permanent is easy.

$\endgroup$

migrated from cstheory.stackexchange.com Sep 30 '15 at 19:33

This question came from our site for theoretical computer scientists and researchers in related fields.

4
$\begingroup$

The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this algorithm to the computation of some polysize permanent.

$\endgroup$
  • $\begingroup$ Actually problem you stated seems to be in $\mathsf{NP\cap coNP}$. I assume you are ordering prime factors of $n$ in terms of size and so you refer as $i$th prime factor of $n$. Does this have any issue with what you state later? Also what is the $\#P$ algorithm that gives $j$th bit of $i$th prime factor of $n$? $\endgroup$ – Turbo Oct 3 '15 at 11:35
  • $\begingroup$ The distinction between $\mathsf{NP}$ and $\mathsf{coNP}$ disappears when looking at it from the angle of $\mathsf{\#P}$. Your assumption regarding the meaning of $i$ is correct. The $\mathsf{\#P}$ algorithm guesses and verifies the factoring, but only accepts factorings in which the $j$th bit of the $i$th prime factor is $1$. $\endgroup$ – Yuval Filmus Oct 3 '15 at 12:51
  • $\begingroup$ So there is no explicit way to give the permanent? $\endgroup$ – Turbo Oct 3 '15 at 13:04
  • 1
    $\begingroup$ The proof of $\mathsf{\#P}$-completeness of the permanent gives an algorithm for constructing the permanent. Anything more explicit would be masochistic. $\endgroup$ – Yuval Filmus Oct 3 '15 at 13:05
  • 2
    $\begingroup$ @Turbo No, I gave you an algorithm, using the standard amount of detail. $\endgroup$ – Yuval Filmus Oct 4 '15 at 2:03

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.