P/NP is a direct consequence of computer science. In the days where computers remained as simple as Turing Machines, humans remained the backbone of problem-solving. However, as the complexity of computers increased, devices such as calculators and arithmetic-based algorithms emerged, and certain fields of math became reliant upon computers for calculations. This advancement shortened computation times for certain problems, but soon a complication made itself known. Computers are brilliant at arithmetic, but mathematics reaches far beyond computing simple functions like square roots or logarithms, and as a result converting math into a computer program that can solve the problem is incredibly difficult. Even my calculator faces increasing running times as the integrals become more complex, and I’m only in Calculus II. As a result, algorithms are only useful in certain situations; the solving of Fermat’s Last Theorem and the Poincaré Conjecture involved almost no computer work, yet algorithms solved two other great problems, the Four Color Theorem and the Kepler Conjecture. P/NP addresses both whether or not any problem can be solved using a computer and if there is an efficient way to compute the answers.

What is an algorithm? According to Ian Stewart, it's not an answer, but rather the formula for a solution. Algorithms are great for computing simple arithmetic solutions, but there is one problem: sometimes an algorithm is too complex or too slow to yield an answer. Just like some Turing Machines aren't decidable (they won't halt), computers will run for billions of years before they can evaluate, using a given algorithm, every possibility for certain problems. This in turn raises the question of whether or not more efficient algorithms exist for these problems. 

Of course, there's a catch. Finding more efficient algorithms is incredibly difficult: finding the time it takes to reach a solution is simple, but trying to decide how efficient existing algorithms are and finding a more efficient algorithm are where the difficulty arises. If we don’t know what the other algorithms are, we can’t evaluate efficiency. For this reason, computer scientists and mathematicians broadly classify problems into “easy” and “hard;” if the length of time it takes to compute a solution using a given algorithm increases slowly as the size of the input increases, the problem is easy. Unfortunately, most problems appear to be hard. This dichotomy can be written as P/not-P. In the simplest, most-brutish way, P/NP will be a proof that either at least one “hard” problem exists, or that it doesn’t. A P algorithm is what I previously defined as an algorithm to an “easy” problem; P stands for polynomial. An algorithm has a polynomial time if the number of steps to an answer is proportional to a fixed power.

Most problems and algorithms, however, are classed as not-P, which does not simplify to NP. There are numerous subclasses to not-P, including E and NP. Most algorithms of the class not-P are inefficient, barring a few which cheat the system. For example, E stands for the subclass of exponential algorithms. In an E algorithm, the number of steps to an answer is proportional to a constant raised to a variable power. Rarely, not-P algorithms can be more efficient than P algorithms, as is the case of an algorithm which determines whether or not a number is odd or even, a problem of the class of constant time. At most, the running time is six, as it looks at the last digit and looks for a 0, then a 2, then a 4, then a 6, then an 8 (in all of these cases the algorithm would output odd), or finally output odd if the previous five steps fail.

One of my favorite P problems is sorting a list of words in alphabetical order, using the ‘bubble up’ method. It's not an efficient algorithm, but it's fun and easy to do without a computer. It can be seen to the right.

There are multiple common examples of class E problems as well. The most famous of which is referred to as the traveling salesman problem, in which a salesman has to travel to an n number of cities and wants to find the shortest route between them. A naive way to solve this problem is to list all of the possible routes. With n cities, there are n factorial, or

n! = n (n - 1) (n - 2) (n - 3) ... 3 x 2 x 1

possible routes. This is undoubtedly a class E problem, and running this through a computer would take a long time to solve. There is a better way to do the problem, and it allows for the problem to be solved in exponential time. It’s called the Held-Karp algorithm, and finds the shortest path in only 2nn2 steps when the number of the cities is sufficiently large. This algorithm is still technically “inefficient,” but it demonstrates the crucial point that using a bit of cleverness and tricks, the computation time for problems can be shortened dramatically. Yet, all of the algorithms for the traveling salesman problem are class E algorithms. Do no efficient algorithms exist, or have we not found the cleverest trick?

That is the question of P/NP. NP stands for nondeterministic polynomial time, or the idea that no matter how long it takes to find an answer to a problem, the solution is checkable in polynomial time. The implication of that statement is that, if a solution can be run backwards to check it in P time, then there must be an algorithm to find that solution in P time. Right now, one of the most popular methods to solve NPs is simply by guessing. The easiest way to explain why this method is not preferable is to use an example of prime factorization. Let's try to factorize 987654321.

Using a table of primes, I can verify that 379721 is a prime number, so the prime factorization of 987654321 = 3 x 3 x 17 x 17 x 379721. How long would it have taken if the factorization went something like 1117 x 721117 x 110580196711? This is the problem with trying to find a more efficient algorithm; there's a lot of trial and error.

There are four possible solutions and implications of the proof, and how to prove which one it is. When that mystical day comes, there’s technically a 25% chance of any of the following being the baseline of the proof:

1. P = NP: If this is the case, it is possible to find fast, efficient algorithms for everything. Cancer can be cured by running specific gene sequences through computers, facial recognition can replace every ticketing system, and anyone can solve any problem.

2. P ≠ NP: The world doesn’t change. Mathematicians remain useful, and while there will always be problems we cannot solve, human curiosity and the very characteristics the human race uses to distinguish itself remain intact. Unshockingly, most mathematicians favor this option.

3. P = NP without a specific example: This sounds the same as option one, but it allows for the world to remain unchanged. Mathematics often doesn’t provide existence proofs which are constructive; if this were the proof, it would state that P = NP but without any indication of what a P = NP algorithm would be. Mathematics would scramble with more fervor to find P = NP algorithms, now that there is concrete proof they exist.

4. P/NP: The problem is undecidable. The Gödel Incompleteness Theorem makes this option entirely possible. However, the implication of the Gödel Incompleteness Theorem is that whatever cannot be proven is true, which provides an interesting conundrum; I’m not sure how that is resolved, but that would generate the same type of situation as in the previous possible result, as mathematicians would turn away from trying to prove that P ≠ NP to finding P = NP algorithms.

The current popular theory of how to solve P/NP involves what is called an NP-complete problem. When Stephen Cook first proposed the idea of P/NP, he realized quickly that which NP problem he worked on didn’t matter. Using a restrictive situation known as 3-SAT, he deduced that there is a group of problems for which one P algorithm being found to solve one of the problems implies that a P algorithm can solve all of the problems. Essentially, proving one proves all. Currently there are over 300 NP-complete problems available for someone to prove whether or not P = NP, in fields varying from economics and string theory to computer games. But what does a world where P=NP look like?

Biologists would know why a certain mRNA sequence causes a protein to fold into a specific shape, and an algorithm can allow for almost infallible disease prevention and curing. Physicists can find the minimum energy state for a complex system, economists can make optimal decisions in the market, and all of the problems deemed unsolvable by the Gödel Incompleteness Theorem are suddenly solvable. All of the millennial problems will be solved. This application to real life is what makes P/NP so completely unique; yes, finding an answer to the Riemann Hypothesis would be cool, and yes Fermat’s Last Theorem was extraordinary, but neither of these problems would completely alter the way the world functions. There is one more very large complication of P=NP, one that rattles my very core. 

If P = NP, then we live in a world where “there would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett” (Nazaryan).

Luckily, the conclusion of the math world is that P ≠ NP. Scott Aaronson, a professor at MIT, even came up with ten possible arguments for why it is logical:

1. It’s been over fifty years, and no one has found a proof.

2. In practice, no fast algorithms for complex problems have been found that work in every instance.

3. The proof will need to look inside and not relativize things that are nearly impossible to observe or not relativize.

4. If P = NP, then a large number of assumptions we have regarding problem complexity is wrong.

5. The elements of each group (E, P, NP, etc.) contain distinct values; rather, they don’t contain the exact same set of values.

6. The only algorithms we have for NP problems are ones which rely on specific algebraic circumstances. There appears to be no way to generalize them.

7. We can prove superpolynomial lower bounds, but not on a circuit size. This somehow implies that P≠ NP.

8. Based on the grounds, a proof for P = NP should be easy to find, whereas a proof for P ≠ NP should be hard to find.

9. There is no human ingenuity, no creative leaps, if P = NP.

10. If you believe P ≠ NP, either you’re right or you’re allowed to reap the benefits of P = NP.

Aaronson’s eighth argument speaks to the argument made by Fortnow in The Golden Ticket. In order to prove that P ≠ NP, it must be proven not only that no algorithm exists that makes P = NP, but also that no such algorithm will ever exist. How can anyone presume to know the future, given the rate that technology improves? It is for this reason, along with the philosophical argument of the ninth statement, that pulls mathematicians to P ≠ NP. Speaking from a general and personal perspective, while I believe that a cure to every cancer that works on every person would be extraordinary and that all of the positive impacts of P = NP would benefit society immensely, I cannot look beyond to what P = NP states about the human race.

If there is an algorithm that can create amazing novels and glorious symphonies and solve every other problem, scientific, artistic, or otherwise, then what’s the point? Why do I bother learning about these math problems if there will one day be a computer program that can do all of them and more for me? While P ≠ NP is an imperfect world, it allows for the definition of human existence, for scientific inquiry and simply curiosity to continue. A significant portion of my personal philosophy revolves around these ideas, and I’d rather live in an imperfect world where they exist than a perfect world that’s void of them.