<p>Is there a general web repository of reductions between and among various NP problems?  In particular, I'm looking for a direct Turing reduction from integer factorization (candidate for NP-Intermediate, not known to be NP-Complete) to clique (NP-Complete).    </p>

<p>Apologies if this is below the difficulty threshold for cstheory;  I'm a graduate mechanical engineering student by training, so my google whispering skills and resources are somewhat limited (though I am ordering a copy of Arora and Barak!).  </p>

<p>Thanks!</p>

CC BY-SA 3.0
2014-03-05T16:47:38.673Z
Are you aware that Integer factorization is not known to be NP-complete (so you'll not find it in the repository if it exists)? In every case a "direct natural" reduction from integer factorization to clique seems quite hard; you should use intermediate steps: from integer factorization to SAT then from SAT to 3SAT and finally from 3SAT to Clique.
Marzio De Biasi
CC BY-SA 3.0
2014-03-05T17:15:05.933Z
Marzio:  Thanks for the advice!  factorization to SAT to 3SAT to Clique provides a path if no direct route can be tracked down.  Also, I edited the question to reflect the fact that I'm looking for factorization to clique, and not the reverse, since that would be kind of a big deal if someone dropped that here! 

Apologies if I'm out of order!
R Hatcher
CC BY-SA 3.0
2014-03-05T17:52:31.253Z
Marzio:  It was very straight forward to find all of the steps in the reduction chain.  Thanks again!
R Hatcher
CC BY-SA 3.0
2014-03-05T19:05:04.613Z
not exactly the same but as MdB points out a connection that has been studied quite a bit is factoring→SAT & have lots of links on that. SAT works well as a "hub" type NP complete problem such that many problems can be reduced to it and it can be reduced to many problems (wrt actual "direct" reductions).
vzn
CC BY-SA 3.0
2014-03-06T16:17:53.613Z
Is this question related to the recent arXiv article: [A Polynomial Time Solution to the Clique Problem](http://arxiv.org/abs/1403.1178) :-)
Marzio De Biasi
CC BY-SA 3.0
2014-03-06T17:13:09.990Z
LOL, no!  :)  However, thanks to your advice I now have a tool chain now that lets me turn small semiprimes into DIMACs clique files that can be attacked with a solver in a kind-of-acceptable amount of time; maybe they could use it to crack an RSA number and put it beyond doubt!
R Hatcher
<cc.complexity-theory><reference-request>
Turing reduction from integer factorization to clique
R Hatcher
# Turing reduction from integer factorization to clique

(Asked by: username_0 on 2014-03-05)

Is there a general web repository of reductions between and among various NP problems? In particular, I'm looking for a direct Turing reduction from integer factorization (candidate for NP-Intermediate, not known to be NP-Complete) to clique (NP-Complete).

Apologies if this is below the difficulty threshold for cstheory; I'm a graduate mechanical engineering student by training, so my google whispering skills and resources are somewhat limited (though I am ordering a copy of Arora and Barak!).

Thanks!

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: Are you aware that Integer factorization is not known to be NP-complete (so you'll not find it in the repository if it exists)? In every case a "direct natural" reduction from integer factorization to clique seems quite hard; you should use intermediate steps: from integer factorization to SAT then from SAT to 3SAT and finally from 3SAT to Clique.  
> **username_0**: Marzio:  Thanks for the advice!  factorization to SAT to 3SAT to Clique provides a path if no direct route can be tracked down.  Also, I edited the question to reflect the fact that I'm looking for factorization to clique, and not the reverse, since that would be kind of a big deal if someone dropped that here!   Apologies if I'm out of order!  
> **username_0**: Marzio:  It was very straight forward to find all of the steps in the reduction chain.  Thanks again!  
> **username_2**: not exactly the same but as MdB points out a connection that has been studied quite a bit is factoring→SAT & have lots of links on that. SAT works well as a "hub" type NP complete problem such that many problems can be reduced to it and it can be reduced to many problems (wrt actual "direct" reductions).  
> **username_1**: Is this question related to the recent arXiv article: [A Polynomial Time Solution to the Clique Problem](http://arxiv.org/abs/1403.1178) :-)  
> **username_0**: LOL, no!  :)  However, thanks to your advice I now have a tool chain now that lets me turn small semiprimes into DIMACs clique files that can be attacked with a solver in a kind-of-acceptable amount of time; maybe they could use it to crack an RSA number and put it beyond doubt!  

---

## 0 answers

