“Don’t Worry About the Vase”
Deterministic vs. Nondeterministic Algorithm
A deterministic algorithm is one that will have the same output given the same input. A nondeterministic algorithm can have different outputs even given the same input. For example, this could be done if the algorithm makes decisions based off of a random number generator.
Nondeterministic Time
Consider a nondeterministic algorithm executing. Whenever it comes to a “fork” or chance to choose an execution path, imagine the algorithm taking all possible paths concurrently. The idea is a conceptual one not limited to hardware, but if it helps, perhaps imagine the algorithm spinning n different threads for each of the n possible branches. This continues, where each branch will further branch out if it comes to another decision. If we ignore the hardware constraints and assume infinite resources to memory, threads, etc., then we can determine the nondeterministic runtime of the algorithm.
Examples
Let’s consider an example problem of Santa and his eight reindeer. Santa needs to drive his sleigh, but his eight reindeer are rather finicky. They have an exact preferred orientation in the sleigh lineup, and they will refuse to fly unless they’re put in the desired permutation. Since there are 8 reindeer, there are 8! = 40,320 different orderings or permutations. Therefore, an algorithm that randomly guesses different permutations to find the right one based on n reindeer would have a time complexity of both O(n!) (worst case) and 𝛺(1) (best case). However, the algorithm would have a nondeterministic time complexity of Θ(1). Put simply, if an algorithm is nondeterministic (thus has random decisions to make), then the nondeterministic runtime will be equivalent to the algorithms best case runtime. Another way to think about nondeterministic running time is that because it’s the time taken in the best case scenario, it’s also the time needed to verify an answer to an algorithm.
Note: Nondeterministic algorithms are not well suited for every problem though. For example, an algorithm that given a list of integers outputs any duplicates in the list. This algorithm would be Θ(n). Because every element in the list will have to be examined, a nondeterministic algorithm will not fare any better and would have the same runtime.
Polynomial Time
P is the set of all problems that can be solved in polynomial time. Polynomial time algorithms are algorithms that are O(n^k) for some constant k. For example, O(n), O(n^2), or O(n^572). Polynomial time is the defacto standard for problems. If a problem can be completed in polynomial time, then it is said to be “easy,” “fast,” or “tractable.” If it cannot be completed in polynomial time, then it is said to be “hard,” “slow,” or “intractable.” This is an important point because problems that are intractable must often be approached in a very different manner than tractable problems. There are toolkits of techniques to solving such problems, and often the best that can be feasibly done is to solve a simpler version of the problem. In the post on function growth, we examined a series of common function growths. We can see that constant, logarithmic, linear, quadratic, and cubic times all fall under the polynomial time umbrella. However, exponential, factorial, tetration, pentation, and hexation times do not.
Nondeterministic Polynomial Time
NP is the set of all problems that can be solved in nondeterministic polynomial time. Nondeterministic polynomial time algorithms are simply algorithms that have a nondeterministic time complexity of O(n^k) for some constant k. It can often provide insights to recognize when a problem can be solved in NP time even if it can’t be solved in P time.
NP-Hard and NP-Complete
NP-Hard is the set of all problems in which all member of NP can be reduced to in polynomial time. Essentially, NP-Hard problems are at least as hard as the hardest problems in NP.
NP-Complete
NP-Complete is the set of all problems that are both in NP and NP-Hard.
Note: Technically P, NP, NP-Complete, and NP-Hard only apply to decision problems where the answer is a boolean true or false value. However, most problems can be converted to a decision problem with a non-significant amount of work.
P = NP
It is trivial to see that any problem in P is also in NP. However, the question that arises is if any problem in NP is also in P. This problem has proved rather difficult to answer since it was asked nearly 50 years ago. The problem is generally referred to as P versus NP and is one of the top problems in computer science today.
Note: For a more in-depth explanation of NP-Hard and NP-Complete, see this excellent stackoverflow answer.