by Robin Yadav
On May 24th, 2000, the Clay Mathematical Institute announced the Millennium Prize Problems. These seven problems are currently the most difficult problems in mathematics and will have profound implications if they are solved. So far, only one of these seven problems has been solved which is a testament to their difficulty. I find the “P vs NP” problem one of the more fascinating and understandable problems on the list. Also, if someone finds an answer to this problem it will have a deep impact on society and human civilization.
What is P vs NP
Essentially, P vs NP boils down to a problem of sets. In particular, there is a set of problems whose solutions are quickly verifiable(NP). Also, there is a set of problems that are easy to solve(P). So, P vs NP asks whether the set of problems that are easily verifiable falls into the set of problems that are easy to solve.
For example, if someone asks you to glue together a glass cup after it falls and shatters on the floor, that would be a very difficult problem. However, it is very easy to check whether the shattered pieces are glued back properly to form a glass. Since it’s a problem that is easy to verify but difficult to solve, it’s classified as “NP”. On the other hand, a “P” problem is if someone asks you to just count the number of large shattered pieces, which is relatively easier than putting them back together.
P = NP or P ≠ NP?
Furthermore, “P” and “NP” are computer science terms that are based on computational complexity. Formally, “P” stands for a problem that can be solved in polynomial time. Meaning that the time to solve the problem is a polynomial function. For example, you have a list of N items on a shopping list and N items in your cart and you have to locate each item. The time it will take you is N(items on the list) * N(items in cart) or N^2(a polynomial function). Currently, most sorting algorithms are efficient enough to sort in polynomial time.
“NP” stands for Non-deterministic polynomial problems and usually take exponential time to solve. For example, if you have to guess an N digit code to enter a room, the time it would take is 10^N(since you have 10 possible numbers per digit). This is a very long time and current computing technology isn’t advanced enough to solve NP problems involving large numbers in a reasonable time.
In terms of computing algorithms, P vs NP questions whether some problems are solvable in polynomial time. Are NP problems just P problems that we haven’t found good solutions for(P = NP)? Or are NP problems intrinsically challenging to solve and no algorithms exist to solve them in polynomial time(P ≠ NP).
An answer for “P vs NP” will impact science and humanity in many ways. Important problems in Computer Science and other fields fall into the “NP” category. Encryption that keeps our information safe uses an NP problem. Typically, two very large prime numbers are multiplied together to form an encryption key that is very hard to break. Prime factorizing a number, especially if it large is an NP problem that will take thousands of years to solve on current computers. However, if P is proven to be NP then we know that some algorithms exist to find those prime numbers in a reasonable time. This makes all of our current encryption techniques obsolete since an algorithm for cracking the encryption can be found. Other problems such as predicting the structures of proteins from amino acids or finding an efficient layout for transistors on a chip are all NP problems.
“P vs NP” is a fascinating problem that will greatly affect our technology if it’s solved. I personally really enjoy just thinking about this problem. Sometimes when I get stuck on a very difficult math problem, I ask myself, “Is this even solvable???” Although the problems I’m doing are definitely not NP difficulty. I feel as though part of my experience is reflected in the P vs NP dilemma. Part of why I am so intrigued by “P vs NP” is that I enjoy solving math problems that I find difficult and challenging. Encountering difficult problems motivates me to work harder and think outside of the box to form a solution. Most importantly, mathematicians and scientists are continually pushing the barrier of knowledge despite facing difficult problems with their work. “P vs NP” will no doubt change how we approach solving problems and acquire knowledge.
Are you a high school student who dreams of a life in science, technology, engineering, art & design, math, or all of the above?
Science World is now accepting applications for our innovative multi-year after-school program Future Science Leaders. Successful applicants will attend weekly sessions with their science-loving peers, engage with STEAM professionals and complete challenging hands-on activities and projects.