-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ geometric complexity theory by Mulmuley is one of them.. $\endgroup$ – singhsumit Feb 3 '12 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 Duck Feb 7 '12 at 20:15
10
$\begingroup$

You might be interested in Scott Aaronson's talk "Has There Been Progress on the P vs. NP Question?" (earlier version)

$\endgroup$
5
$\begingroup$

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) :-)

$\endgroup$

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