Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Yuval Filmus Dec 19 '13 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. –  Nathan Jordan Dec 22 '13 at 10:07
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
fyi the paper link is now 403 forbidden –  vzn Sep 17 '13 at 16:23
1  
Regarding your second paragraph: Cook's theorem shows that any problem in NP can be reduced to SAT. –  Yuval Filmus Dec 19 '13 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 '13 at 15:56
add comment

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!).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.