History of the Problem

In the 1970s, computer scientists began tackling various real-world issues with their cumbersome machines. Initially, they devised slow solutions, but over time, they learned to optimize their approaches for greater efficiency.

To illustrate the difference between slow and fast solutions, consider the task of locating a number within an array. A basic method would involve checking each element sequentially—a process with a time complexity of O(N), where N represents the number of elements.

However, if the array is sorted, we can utilize a more efficient strategy. By examining the middle element first, we can determine whether to search the left or right subarray based on its relation to the target number. This results in a logarithmic time complexity of O(logN).

This distinction between slow and fast algorithms is critical in understanding how computers solve problems. While we have efficient solutions for tasks like multiplication and sorting, certain challenges, such as chess or sudoku, remain unsolved quickly.

The Travelling Salesman Problem serves as a prime example of a complex issue. For those in the field, you might recall the question: Given a list of cities and the distances between them, what is the shortest route that visits each city exactly once before returning to the starting point?

Understanding P vs NP

In this context, P represents problems with reasonably quick solutions, while NP encompasses those for which solutions can be verified quickly, even if they can’t be easily solved. The P vs NP question asks whether all NP problems can also be classified as P problems.

The concept was first articulated by Stephen Cook in 1971 in his foundational paper “The Complexity of Theorem Proving Procedures.”

To clarify:

• P (Polynomial Time): Problems solvable by an algorithm in polynomial time.
• NP (Nondeterministic Polynomial Time): Problems where a solution can be verified in polynomial time but lacks a known quick solution.

For example, while there is no known polynomial time algorithm for solving sudoku, verifying a solved sudoku can be done quickly.

Let’s also discuss polynomial time algorithms. Such algorithms solve problems within a timeframe that doesn’t grow exponentially as the number of variables increases. For instance, the time complexity for the Travelling Salesman Problem is O((n^2)*(2^n)), meaning that as the number of cities increases, the time required to solve the problem increases dramatically.

The Core Question: Is P Equal to NP?

The fundamental question is whether every NP problem can also be solved in polynomial time. This is what you need to uncover to claim that million-dollar prize.

In the diagram above, we see scenarios for when P equals NP versus when it does not. Additionally, here are some essential terms:

• NP-Hard: Problems that are at least as challenging as the hardest NP problems.
• NP-Complete: Problems for which any solution can be verified quickly and can be solved using brute-force methods.

What If P Equals NP?

If P indeed equals NP, then NP-hard problems could be solvable within polynomial time. One NP problem has already been resolved in polynomial time—the primality problem, which asks: Is a given natural number prime?

Other NP problems include vehicle routing (TSP), circuit design (SAT), job scheduling, and protein folding. If NP problems can be categorized as P, we could potentially address numerous global challenges, from business optimization to medical breakthroughs.

Problems like TSP and sudoku share a commonality at their core, making them significant in the NP landscape. Remember, if we find a solution for one NP-complete problem, we can solve all NP-complete problems.

Proving P = NP would not only mark a monumental milestone in mathematics but could also revolutionize fields such as biology and chemistry, potentially compromising current encryption systems and data security. And, of course, you’d win a million dollars!

Alternatively, you could prove that P does not equal NP and still walk away with a million.

With that said, best of luck on your mathematical journey!

New to Medium.com? For just $5 a month, you can read unlimited articles from every author on Medium. Become a member here. Click the link below.