Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is it possible that P vs NP is not the real problem?

, , No Comments
Problem Detail: 

Lets assume that I found a polynomial solution for Hamiltonian path problem. It is known that you can reduce this problem to SAT. How ever it will be a special case of SAT. Just the case where there is only one interpretation that satisfies that Boolean formula.

Can you extends this special case for general case? If not, how would you define the NP group now?

Are all the NP-complete problems have a strong reduction? If I solve one NP-complete problem, can I state that I found the solution for P versus NP problem. Or it will brake the very definition of P versus NP as some problems will remind part unsolved.

In one case I know for sure that I found the P versus NP problem solution - If I can find polynomial solution for SAT as it stays in the top of the pyramid. But is it true for all the rest of the problems?

Asked By : Ilya_Gazman

Answered By : Shaull

You don't seem to have a correct grasp of the concept of NP-completeness. Every NP complete problem has a reduction to every other NP complete problem. That is, there is a poly-time reduction from SAT to HAMPATH.

Thus, if you have a polynomial solution for HAMPATH, you can solve any case of SAT in polynomial time, so P=NP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18290

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback