Why Is Complexity Theory Important

If you've ever read about Complexity Theory and the famous "P vs NP question", you've probably thought that it is a way for the mathematicians to have fun. They have found this problem with no solution and try to come up with the right approach to get to the bottom of it. In other words, it is difficult to see the practical value of solving this problem other than a bunch of scientists feeling happy. In reality, we all will benefit a lot if someday someone finds the solution.

Before we get back to the importance of solving the problem, we need to understand what it means. Without getting into too much of details, we can say that there are two kinds of problems - those that require a reasonable amount of time to solve (N) and those that can take us forever to solve (NP). The major feature of the NP problems is that they are easily verified but way too difficult to solve. In other words, if someone says that the answer to this question is 27, 567, we can easily check if it's true or not. However, the process of giving multiple attempts to find that answer on our own would take a very long time. The biggest question is whether any problem that is easily checked can also be easily solved (are all NP problems always P?).

If someone finds the strategy to solve any NP problem within a reasonable amount of time (that P=NP), the humankind will discover the ultimate algorithm for solving any problem. The society we live in would become more efficient in many ways. Consider having better transportation schedules and manufacturing cycles. It would lead to discovering new cures for terminal diseases like cancer by creating effective computational models.