Columbia Science Review
  • Home
  • About
    • Our Team
  • Blog
  • Events
    • 2022-2023
    • 2021-2022
    • 2020-2021
    • 2019-2020
    • 2018-2019
    • 2017-2018
    • 2016-2017
  • Publications
  • COVID-19 Public Hub
    • Interviews >
      • Biology of COVID-19
      • Public Health
      • Technology & Data
    • Frontline Stories >
      • Healthcare Workers
      • Global Health
      • Volunteer Efforts
    • Resources & Links >
      • FAQ's
      • Resource Hubs
      • Student Opportunities
      • Podcasts & Graphics
      • Mental Health Resources
      • Twitter Feeds
      • BLM Resources
    • Columbia Events >
      • Campus Events
      • CUMC COVID-19 Symposium
      • CSR Events
    • Our Team
  • Contact

What is P versus NP?

3/28/2021

0 Comments

 
Picture
Kevin Wang

In 2000, the Clay Mathematics Institute published the Millenium Prize Problems. These were seven mathematical problems, and solving any one of them came with the award of one million dollars. However, they were also some of the most complex, unsolvable problems of the past few centuries. Many appear intimidating just from their name—the Riemann Hypothesis, the Yang-Mills Existence, and Mass Gap, just to name a few. The very first problem on the list, though, looks easy enough, almost like a middle school algebra equation. It is simply titled “P = NP.” 

It is now 2021, and the P = NP problem has yet to be solved. Why is this so? What is it about this statement that even the greatest mathematical minds of the last two decades cannot solve it?

The actual meaning of the P = NP problem is much more complicated than it appears. It is a statement about different types of problems, or tasks. In computer science, a problem is anything you can get a computer to do, such as printing out a series of numbers, calculating an expression, or searching the internet. The solutions to these problems are called algorithms, and the field of computer science is heavily concerned with something called algorithmic complexity—how long it takes for an algorithm to run and a problem to be solved. However, this isn’t simply measured in seconds or minutes, but rather in relation to the number of elements an algorithm must operate on.

Take, for example, an algorithm that must sort a list of unordered numbers. It makes sense that the more elements, or numbers, there are, the longer this algorithm takes to solve the problem. Scientists have devised clever algorithms such as Merge Sort that are able to sort the elements in O(logn) time, meaning the runtime is proportional to log(n), with n being the number of elements to be sorted. 

Picture
The logarithm function. As n (the number of elements) increases, log(n) (the time required) increases, but at a decreasing rate. As a result, very, very large lists of numbers don’t require too much time to be sorted.

However, other problems have significantly larger complexities. Prime factorization, or reducing any integer down to the product of prime numbers, doesn’t sound too difficult. However, the most efficient existing solution is O(xn), or proportional to an exponential function. This grows much faster than the log function, and as n gets very large, the runtime will skyrocket.

Picture
The exponential function. As n increases, xn begins to increase very quickly. The algorithm quickly reaches a very long runtime.

A threshold used for algorithmic complexity is polynomial time—that is, whether an algorithm runs in O(nx) for some x. This is clearly a faster growth rate than logarithmic or even linear functions, but much slower than other functions such as exponential or factorial functions, regardless of the base x.

This is where P = NP comes in. P and NP are both sets of problems—essentially, just groups. P stands for “polynomial time” and NP stands for “non-deterministic polynomial time.” Specifically, a problem in P is something that can be solved in polynomial time—whether the best possible algorithm to run it on is at most polynomial. A problem in NP is something that can be verified in polynomial time—given any solution, how long it takes to make sure that that solution is correct. The question of P = NP asks if these two sets are equal—in other words, if every problem that can be verified in polynomial time can also be solved in polynomial time.

This distinction is important. The prime factorization is one such example. Verifying a given solution is extremely easy, and can be done in far less than polynomial time — simply multiply together all of the factors and check that it yields the correct number. Solving the problem, as we have seen, has yet to be done in polynomial time. However, we have yet to actually prove that this is the best possible solution to prime factorization. Therefore, we are certain that prime factorization is in NP, but we are uncertain if it is in P. In order to prove P = NP, we would need to prove that every problem in NP is also in P, and vice versa. This appears unlikely, but no one has formally proved that it is either true or false.

Why do we even ask this problem? Proving P = NP (or the opposite) would have important implications for different fields. For example, in cryptography, the study of making code and passcodes, most solutions and codes are easy to verify once you know the code. However, if we proved that P = NP, then that would mean that these codes are solvable in less than polynomial time — meaning someone could figure out your email password without too much time. Solving P=NP would have important effects in many fields, from algorithm development to biology. 

However, after decades, we have yet to solve the problem, and it doesn’t look like we’re getting any closer. Perhaps this question will always remain a mystery.

​
0 Comments



Leave a Reply.

    Categories

    All
    Artificial Intelligence
    Halloween 2022
    Winter 2022-2023

    Archives

    April 2024
    January 2024
    February 2023
    November 2022
    October 2022
    June 2022
    January 2022
    May 2021
    April 2021
    March 2021
    February 2021
    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    July 2020
    June 2020
    May 2020
    April 2020
    March 2020
    February 2020
    January 2020
    November 2019
    October 2019
    April 2019
    March 2019
    February 2019
    January 2019
    December 2018
    November 2018
    October 2018
    April 2018
    March 2018
    February 2018
    November 2017
    October 2017
    May 2017
    April 2017
    April 2016
    March 2016
    February 2016
    December 2015
    November 2015
    October 2015
    May 2015
    April 2015
    March 2015
    February 2015
    January 2015
    December 2014
    November 2014
    October 2014
    May 2014
    April 2014
    March 2014
    February 2014
    December 2013
    November 2013
    October 2013
    April 2013
    March 2013
    February 2013
    January 2013
    December 2012
    November 2012
    October 2012
    April 2011
    March 2011
    February 2011
    September 2010
    August 2010
    July 2010
    June 2010
    May 2010
    April 2010
    March 2010
    February 2010
    January 2010
    December 2009
    November 2009
    July 2009
    May 2009

Columbia Science Review
© COPYRIGHT 2022. ALL RIGHTS RESERVED.
Photos from driver Photographer, BrevisPhotography, digitalbob8, Rennett Stowe, Kristine Paulus, Tony Webster, CodonAUG, Tony Webster, spurekar, europeanspaceagency, Christoph Scholz, verchmarco, rockindave1, robynmack96, Homedust, The Nutrition Insider
  • Home
  • About
    • Our Team
  • Blog
  • Events
    • 2022-2023
    • 2021-2022
    • 2020-2021
    • 2019-2020
    • 2018-2019
    • 2017-2018
    • 2016-2017
  • Publications
  • COVID-19 Public Hub
    • Interviews >
      • Biology of COVID-19
      • Public Health
      • Technology & Data
    • Frontline Stories >
      • Healthcare Workers
      • Global Health
      • Volunteer Efforts
    • Resources & Links >
      • FAQ's
      • Resource Hubs
      • Student Opportunities
      • Podcasts & Graphics
      • Mental Health Resources
      • Twitter Feeds
      • BLM Resources
    • Columbia Events >
      • Campus Events
      • CUMC COVID-19 Symposium
      • CSR Events
    • Our Team
  • Contact