-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$

closed as not constructive by Artem Kaznatcheev, Tsuyoshi Ito, Jeffε, Jukka Suomela, Lev Reyzin Feb 3 '12 at 14:30

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.