In this post I’d like to quickly clarify the levels in computational complexity theory. Oftentimes there is confusion and misconceptions of the terms P, NP, NP-Complete, and NP-Hard. These classes are evaluated in terms of how easily they can be solved, and how easily their solutions can be verified.
P
P stands for polynomial time. This is the easiest class of problems. They can be solved and their solutions can be verified in runtime which is polynomial to their input size. Take your binary search algorithm for input of size n. It can be solved in O(log n) and can be verified either by running it again, or iterating over the input at O(n). Either way it is verifiable in time polynomial to the given input size.
To summarize for P: solvable -> easy, verifiable -> easy.
NP
NP does not stand for non-polynomial time as one might guess, but instead stands for non-deterministic polynomial time. This is defined as problems which can be solved in polynomial time on a non-deterministic machine. A non-deterministic machine is a theoretical computer (at least at the time of this writing) that is allowed to make a correct guess at each step. NP problems can also be verified in deterministic polynomial time just like P. Therefore, P is a subset of NP, so any problem in P is also in NP due to their verification property.
To summarize for NP: solvable -> doesn’t matter, verifiable -> easy.
NP-Complete
The big question on everybody’s mind is does P = NP? At the moment we don’t know. But the implication is that if true, then there is a deterministic polynomial time solution for every problem in NP, and therefore, P and NP are the same. If P does not equal NP, then P is a strict subset of NP, and there are a class of problems which are verifiable in deterministic polynomial time but not solvable in deterministic polynomial time. This class is called NP-Complete. This class would disappear if P = NP is ever proven.
NP-Complete assumes that P does not equal NP. An example of an NP-Complete problem is the 3SAT problem, where we have a boolean expression formula in conjunctive normal form. It looks like this: (x || !y || z) && (!x || !!y || z) . Finding a solution to such a problem might require a brute force approach which results in a runtime that is not polynomial to the given input size. However, the solution is easy to verify, by just plugging in the values in O(1) time.
To summarize NP-Complete: solvable -> easy (if P = NP) or hard (if P != NP), verifiable -> easy.
NP-Hard
The last class of problems are NP-Hard. At the moment, they fall outside of P since it is not proven that P equals NP. NP-Hard means that the solutions cannot be verified in deterministic polynomial time. In layman terms, there are no easy or efficient ways to solve or to verify the solution. Examples of NP-Hard problems include the traveling salesman problem and then knapsack problem.
Looking at the knapsack problem, we see it has a runtime of O(nW), where n is the length of the array of items and W is an integer representing the maximum capacity. The solution cannot be found in deterministic polynomial time, since the size of W as input is considered in bits as log W. Adding 1 to W only increases the input size when it causes us to add an extra bit. However, to solve the Knapsack we will need to run n * W operations so increasing W always increases the runtime to solve. More important is to notice the difference between input size and the order of operations to solve knapsack. The difference is not polynomial in size. The input size is n + log W while the runtime is n * W. Plot these on a graph and you’ll see the exponential difference between the input size and the growth rate for the runtime. Concerning the verifiability of knapsack, there is no known way to verify a solution in less than O(nW), so verifying also occurs in non-deterministic polynomial time.
To summarize NP-Hard: solvable -> hard, verifiable -> hard.