0
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Mar 5 '14 at 16:47
  • $\begingroup$ Here's a good starting point for reductions between NP-complete problems: en.wikipedia.org/wiki/Karp's_21_NP-complete_problems . I don't know if there's a natural reduction straight from factorization to clique; there are reductions other than the Cook-Levin one from factorization to SAT, I just don't remember quite how to do that reduction right now. $\endgroup$ – Philip White Mar 5 '14 at 17:06
  • $\begingroup$ 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! $\endgroup$ – R Hatcher Mar 5 '14 at 17:15
  • $\begingroup$ Marzio: It was very straight forward to find all of the steps in the reduction chain. Thanks again! $\endgroup$ – R Hatcher Mar 5 '14 at 17:52
  • $\begingroup$ 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). $\endgroup$ – vzn Mar 5 '14 at 19:05

Your Answer

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

Browse other questions tagged or ask your own question.