What’s P = NP Problem?
Wow, it’s been more than a year since I wrote something in Medium. During pandemic (Covid) like this, writing would be an interesting hobby to start with. I feel that I would understand the topic better since I need to dive deeper into the material first. Well, I’m not an expert, so just enjoy ☺
Recently, I was hooked by a book titled The P=NP Question and Gödel’s Lost Letter. Well, I had no background about Theoretical Computer Science before, so I found this very new and intriguing for me. Like mentioned in the title, the book itself discussed about P = NP problem. This is one of the hardest problems in mathematics, and solving it would grant you one million dollars!
What is P?
Consider one very simple problem: what is the total amount of dollar bills in your wallet.
We can design a very naive algorithm which scans each of the paper money, and sums the amount. For any algorithm, we can calculate the ‘complexity’, i.e. how long will it run for a given input. In our case the complexity will depend on the number of paper in the wallet. If there are 5 $20-bills in the wallet, the machine needs to scan 5 times (very naive algorithm, just for simplification) and sum the amount, so if one scan requires 1 second, then the algorithm complexity is basically 5 seconds.
Our P here refers to a class of problem complexity, which is easily solvable or tractable (link). In mathematical terms, those problem can be solved in a polynomial time (from which P got his name). Our algorithm runs in a polynomial time. Given n dollar bills, it requires n (or n¹) time. Our problem is definitely tractable. Congratulations!
What about NP?
On the other hand, NP refers to a problem whose solution can be easily verified (in polynomial time). Now consider a different problem: how to open this lock?
If owner of the lock told you that the password is 313, you can simply try the password to check whether it’s correct. It’s very fast and easy to verify (obviously still in polynomial time). However, what if you have no information? One naive solution is to simply try every possible combination. One digit has 10 possibilities, so the total number of combinations would be 10³=1000. If one trial requires 1 second, then you need less than 17 minutes to open the lock for sure (it can be faster if you are lucky). Well, what if there are 6 digits? You need more than 27 hours to try all combinations. This is one example of exponential time, which is larger than polynomial time.
The problem above is one example of NP problem. The solution can be easily verified, but the finding the solution takes more than polynomial time. In fact NP got its name from nondeterministic polynomial time. It’s ‘nondeterministic’ since trying random 'guess' only takes polynomial time, but it doesn’t guarantee the correct solution.
More about Complexity
If you have some background in mathematics or computer science, you should have a good understanding of algorithm complexity already. In case you don’t know, I’ll explain a little bit here.
Suppose you have 3 algorithms with different calculation time in the graph (taken from wiki). The x axis is the number of inputs, and y axis is the computation time. In this case, the red and blue algorithms have polynomial time, and the green has exponential time. In computation, algorithm with exponential time simply would not work. Small inputs would still be fine, but the complexity would explode for larger inputs (such as x > 8 in the graph). In real world case, the inputs would be very large in most of the case, so exponential time is definitely a no.
Moreover, although the red and blue algorithms both have polynomial time, the red one is preferable since it has lower order (1) compared to blue one (3). It can be found from the number in the power of x. As you can see in the graph, the computation time of blue algorithm explodes for x > 7.
P = NP Problem?
Now let’s move on the main problem: is P = NP? In other words, if the solution of a problem can be easily verified, then can the correct solution be easily found also? As for now, we don’t know yet, but we can imagine what will happen for each case:
P = NP
If this is true, the impact will be huge! Consider opening lock problem above. It can be generalized into cracking your bank account password, for example. If P = NP, then there would be an algorithm which able to find the password in the polynomial time, which would be disastrous for society.
P ≠ NP
Well, I think most of you will agree that this will be most likely the correct case, although there is no prove yet. Intuitively, not all problems can be solved that easily, such as cracking bank account. Unless some other ways available to get the password (such as knowing the password directly from the person or some smart hacky ways from action movies), one can only try all password combinations, i.e. brute force way. This would take huge amount of time to crack!
Takeaways
I’m not sure whether this knowledge will be directly useful to your life, but at least you now know one of the hardest problems in mathematics. Moreover, I hope some basic knowledge about algorithm would be useful for you, since our world now relies heavily on the algorithm, from your phone to airplanes.
