# Reducing the integer factorization problem to an NP-Complete problem

I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-Complete. Every problem in NP can be reduced to an NP-Complete problem, however I haven't seen any examples for reducing a suspected NPI problem (such as integer factorization) into an NP-Complete problem. Does anyone know of any example of this or another NPI->NPC reduction?

• By the definition of NP-completeness, any problem in NP can be reduced to any NP-complete problem. In particular, Cook's theorem shows that SAT is NP-complete, and so gives you "explicitly" such a reduction. Dec 19, 2013 at 15:19
• @YuvalFilmus I understand that there is a formalization that such a method exists, however I was looking for a more concrete algorithmic approach similar to, say the reduction of the Hamiltonian Cycle problem to the Traveling Salesman problem. Wherein you can set all the edge weights to 1 and run TSP on the graph and check if the distance traveled is greater than |E|. Something like that I suppose.
– N J
Dec 22, 2013 at 10:07

For example, there is a neat classic reduction of factoring to SAT which is also a source of presumed "hard" SAT instances. Basically one uses EE ideas for binary multiplication encoded into the SAT circuit. Think of binary multiplication as an addition of a series of left shifted multiplicands, each "masked" (ANDed) by the bits of a multiplier. The additions can be performed by a binary addition circuit which is a series of full adders.

A talented undergraduate could build this algorithm. I don't know where it was first proposed or implemented in the literature. I would be interested to hear any references.

See e.g. Satisfy This: An Attempt at Solving Prime Factorization using Satisfiability Solvers by Stefan Schoenmackers and Anna Cavender which lays it out in detail. Also the DIMACS SAT challenge starting in the late 90s had factoring instances that were generated by some researchers but possibly the algorithm was not written up seperately in a paper during that era.

• fyi the paper link is now 403 forbidden
– vzn
Sep 17, 2013 at 16:23
• Regarding your second paragraph: Cook's theorem shows that any problem in NP can be reduced to SAT. Dec 19, 2013 at 15:19
• right, the Cook proof is a general theoretical existence proof and there are more direct/specialized conversions/algorithms often constructed between NP complete problems (usually with better "overhead"). was referring to the latter.
– vzn
Dec 19, 2013 at 15:56

Just to be absolutely clear, Integer Factorization is not known to be NP-intermediate, just suspected to be based on the lack of either NP-completeness proof or polynomial-time algorithm (despite lots of work put into both). I don't know of any natural problem (i.e. not constructed by Ladner for the proof) that is definitely NP-intermediate if P and NP are different.

Okay, after that disclaimer, Graph Isomorphism is another likely candidate for a natural NP-intermediate problem. There's a simple polynomial-time reduction from it to Subgraph Isomorphism - just leave the graphs the same! Graph Isomorphism is just the special case of Subgraph Isomorphism where both graphs have the same size. The final touch is that Subgraph Isomorphism is NP-complete.

Apart from that, there is always of course the not-so-informative reduction promised by the Cook-Levin Theorem, we known that any NP-intermediate problem has some nondeterministic polynomial-time Turing Machine that decides it, and we can convert this into an instance of SAT (just have to build the TM!).