There are of course many unsolved problems. A solved problem is that of writing a Wikipedia article containing many of the unsolved problems. That is done, and it is an excellent collection.
This is by no means a rigorous introduction to the question. It might even have a lot of mistakes. This is just how I understand the problem so far, and I’d like to compare it to what I will get to know later on. I am one of those who believe that not understanding a thing perfectly can help a lot.
One of the seven Millennium Prize problems in mathematics and theoretical computer science is the P vs. NP conjecture, which I’ll briefly talk about today.
Wikipedia has a great article containing lots of information of what this really is about. It is by no means my only source though and I really recommend checking it out. CMI has a great, somewhat intuitive informal introduction to the problem in general.
First thing first: to understand this it is necessary to understand the branch of computer science and mathematics known as ‘(computational) complexity theory’. It is dealing with the cost of solving problems computationally. That is, it studies the complexity of problems. Now let us define two classes of problems (these definitions are what I’d like to somewhat improperly call axiomatic, and therefore not to question for the sake of the problem itself).
Class P — Here we put all problems that can be solved by a systematic approach in a finite number of steps.
Class NP — This class is a superset of the P class, and it contains all the problems that can be solved in a non-deterministic way in a finite number of steps. These classes are often described using Turing machines.
The big question is: Is P equal to NP? If that is the case, it would mean that given a problem having solutions that are easy to verify, we could also find an easy way of computing that answer. Many computer scientists believe the answer to this question is no, but it is still formally not proved, and a prize tag of $1,000,000 is set by the Clay Mathematics Institute for a proof.
To understand this better I like to think of cryptography, where there are processes we can’t reverse. If P=NP, that would mean we could, and therefore it should be easy to crack our “safe” codes.
By the way, Sudoku is NP-complete!
