Prerequisites. You should be familiar with:
- Nested loops
- Recursion
The easiest way to learn this is by learning from examples. Let us consider two problems that we will be discussing throughout this article.
Problem-1: Sorting
Example: Problem — sort the array [7,2,5,1,9]. Output — [1,2,5,7,9].
Problem-2: Subset Sum
Example: Problem — Given a set of integers {2, 4, 6, 9} and a target sum of 10, is there a subset of the given set that adds up to 10? Output — “Yes” ({4, 6}).
Now, let us analyze the problems concerning two criteria.
Has a polynomial time solution?
Meaning if the problem can be solved in polynomial time, i.e., O(n²), O(n³), etc. (not O(2^n), O(3^n) etc.).
Problem-1 Sorting: Yes. Even not-so-great bubble sort is O(n²).
Problem-2 Subset Sum: No. We do not know any polynomial time solution to this problem yet. You cannot find an answer with nested, triple-nested, or n-nested loops (with n being a constant). The best known algorithm is O(2^n).
Can a given solution be verified in polynomial time?
Problem-1 Sorting: Yes. If I tell you that sorting [7,2,5,1,9] will produce [1,2,5,7,9], you can verify in O(n) time whether I am correct (just need to check that no number is smaller than the previous number).
Problem-2 Subset Sum: Yes. If I tell you that the sum of the subset {4, 6} from the set {2, 4, 6, 9} matches the target sum (10), you only need to check if 4 + 6 equals 10, which is very straightforward.
Let us summarize the discussion in a table:
It is obvious that any problem that can be solved in polynomial time, a given solution can be verified in polynomial time (If column B is Yes, C will always be Yes). For example, if I tell you that the sorted output of [7, 2, 5, 1, 9] is [1, 2, 5, 7, 9], you can simply sort the given array (in polynomial time) and compare your output with my given solution to verify.
Now, based on these two properties, we can understand the classes P and NP.
P: Has polynomial time solution.
NP: May or may not have a “known” polynomial time solution. But a given answer can be verified in polynomial time.
Therefore, any problem that is in P, also is in NP. This fact might seem counterintuitive since P problems are often perceived as ‘easy’ while NP problems are seen as ‘hard,’ potentially leading to the misconception that easy problems are included in the hard problems. Notice that it is good enough for a problem to be NP if it is verifiable in polynomial time (does not require to be solvable in polynomial time). Therefore, P becomes a subset of NP. Both sorting and subset sum are NP, but only sorting is P (subset sum is not P). I believe the scientific community did a poor job in naming these classes!
!!!Warning!!! Known vs Unknown!
Notice that saying “Subset Sum does not have any polynomial time solution” would be partially correct. The fact is, there is no “known” polynomial time solution. But it has not yet been theoretically proven whether Subset Sum can or cannot be solved in polynomial time. Therefore, if you hear that some particular problem is NP, you should consider that:
- It could also be in P, and
- Even if it is not in P currently, it has not been theoretically proven or disproven whether it will ever be in P
So, there remains a possibility that someday we may discover that all NP problems can be solved in polynomial time, meaning they are also in P, implying that NP would be a subset of P. If this were the case (and since P is subset of NP), it would mean that P equals NP, which is literally a million dollar quest!
!!!Warning Again!!! Turning Machine!
Whatever we discussed is overall the truth. For theoretical accuracy, one more thing to consider. Whenever we talked about being solvable or verifiable, we meant solvable/verifiable by “deterministic turning machines” (modern day computers we use). Incorporating “Nondeterministic Turing machine” (theoretical machine — no real world implementation) in the discussion would change everything.
