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