Problem Detail: I’m struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Lander’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?
Asked By : Nathan Jordan
Answered By : vzn
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6588
