The P versus NP problem is still open. It seems like there is not a polynomial time solution to these problems, but this hasn't been proven. Either way (whether there is a polynomial time solution or not), there would be major implications to our world.
3 Most Important Points:
If P=NP, then lots of the world's problems would be really really easy to solve. It would make traffic flow much better, for one. BUT it would wreak havoc on cryptography. It would also solve most of the other open problems that have million-dollar prizes!
Even if P != NP, we can solve lots of the specific cases of reasonable sizes, and there would still be lots of interesting things to explore in this type of problem.
Oh … this goes on Sakai. Oh well, this is a fun note to myself that I should look there for interesting stuff about this problem :)