I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this problem so difficult to prove/disprove. Has there been any progress has been made toward resolving it. That is, what approaches have been taken (and failed), and what insights have been made toward possibly finding a solution?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ geometric complexity theory by Mulmuley is one of them.. $\endgroup$– singhsumitFeb 3, 2012 at 7:16
-
$\begingroup$ "I have not failed. I have just found ten thousand ways that won’t work." "How long will it take to find your shoes?" $\endgroup$– Mooing DuckFeb 7, 2012 at 20:15
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You might be interested in Scott Aaronson's talk "Has There Been Progress on the P vs. NP Question?" (earlier version)
$\begingroup$
$\endgroup$
For what concern "... what approaches have been taken and (in all probability) failed ...", see the P-versus-NP Page that collects links to papers/authors that try to settle the "P versus NP" question (in either way) :-)
answered Feb 3, 2012 at 8:14