Menu
I know that P=NP has not been solved up to now, but can anybody tell me something about the following: What are currently the most promising mathematical / computer scientific methods that could be helpful to tackle this problem? Or are there even none such methods known to be potentially helpful up to now? Is there any (free) compendium on this topic where I can find all / most of the research done in this area?
602
Although one-way functions have never been formally proven to exist, most mathematicians believe that they do, and a proof of their existence would be a much stronger statement than P ≠ NP. Thus it is unlikely that natural proofs alone can resolve P = NP.
(i) All NP-complete problems are solvable in polynomial time: Yes. Every problem in NP is polynomially reducible to SAT, and SAT is reducible to every NP-hard problem. Therefore, a polynomial time solution to any NP-hard problem (such as 3Col) implies that every problem in NP can be solved in polynomial time.
If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited.
Now, if P=NP, we could find solutions to search problems as easily as checking whether those solutions are good. This would essentially solve all the algorithmic challenges that we face today and computers could solve almost any task.
An excellent overview appeared last year in Communications of the ACM. I think it became the most downloaded article of CACM ever, so your question may be relevant after all :-)
The Status of the P=NP Problem, Lance Fortnow, Communications of the ACM, Vol. 52 No. 9, 2009
119
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
