2
$\begingroup$

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly?

Edit: I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?

$\endgroup$
1
3
$\begingroup$

A problem $X$ is "NP-complete" if for any problem $Y$ in NP, there is a polynomial-time reduction from $Y$ to $X$. So if there is a polynomial-time algorithm for some NP-complete decision problem $X$, then there is a related algorithm for any problem $Y$ in NP, namely, reduce the instance of $Y$ to an instance of $X$ and use the polynomial-time algorithm for $X$.

$\endgroup$
2
$\begingroup$

Since NP-complete is a subset of NP, the answer to both of your questions is "yes". Suppose you had a deterministic poly-time solution to some NP-complete problem $D$. Then, by the definition of NP-completeness, every problem in NP could be poly-time reduced to $D$ and so would be in P. Since any NP-complete problem is by definition an NP problem, you would then have poly-time deterministic solutions to every NP problem, including those that are NP-complete. (Not to mention that you could then write your own meal ticket.)

$\endgroup$
6
  • $\begingroup$ With your last remark, you are assuming that "polynomial-time" implies "computationally tractable". And even if that were true, turning a super-fast factoring algorithm into food (via money, I presume) is an enormously complex task in itself! $\endgroup$ – TonyK Jul 9 '12 at 16:49
  • $\begingroup$ @TonyK Actually, factoring isn't known to be intractable, but I still maintain that a peer-reviewed article titled "SAT is in P" could be turned into money without much work (certainly much less work than coming up with the result in the first place). $\endgroup$ – Rick Decker Jul 9 '12 at 17:35
  • $\begingroup$ If it's peer-reviewed, everybody will switch to Elliptic Curve Cryptography, won't they? So you have to do it all in secret if you want to pay for your lunch with it. Do you personally have all the skills required? I certainly don't! $\endgroup$ – TonyK Jul 9 '12 at 18:10
  • $\begingroup$ @TonyK: If P=NP, why does switching from RSA to elliptic curve cryptosystems help? $\endgroup$ – Tsuyoshi Ito Jul 11 '12 at 13:30
  • $\begingroup$ @Tsuyoshi: You got me there! $\endgroup$ – TonyK Jul 11 '12 at 13:37

Your Answer

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

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