COMPUTER SCIENCE

P vs. NP — What is the Difference Between Solving a Problem and Recognizing its Solution?

Diving into the most notorious open question in computer science and its far-reaching philosophical consequences.

Eliran Natan
Sep 28 · 11 min read
Image for post
Image for post
William Blake’s Newton (1795)
Image for post
Image for post
NASA scientists with their board of calculations, Life Magazine, 1957
Image for post
Image for post
A dodecahedron as a two-dimensional planar graph. One possible Hamiltonian cycle is shown in red.

Given a Graph, determine whether it contains an Hamiltonian cycle.

“The asymptotic viewpoint is inherent to computational complexity theory, and reveals structure which would be obscured by finite, precise analysis.”

— Avi Wigderson

Image for post
Image for post
An algorithm’s Time Complexity is described as an asymptotical function that is dependent on the algorithm’s input size. A main distinction is made between a Factorial, Exponential, and Polynomial complexity functions.

Algorithms that have a Polynomial Time Complexity are referred to as “efficient”.

Image for post
Image for post
Michael Held, Richard Shareshian, Richard Karp. IBM Archives.
Image for post
Image for post
Dantzig, Fulkerson, and Johnson 49-city tour, Newsweek, July 26, 1954.

A Decision Problem is in NP if its solutions can be efficiently verified.

P is the set of all decision problems that are efficiently solvable. P is a subset of NP.

Image for post
Image for post
P is the set of all decision problems that are efficiently solvable and is a subset of NP. Basic Arithmetic is solvable in Polynomial-time, thus belongs to P. Soduko’s decision problem is in NP, whereas it is not clear whether it is in P. Chess decision problem is outside of NP since there is no efficient algorithm that can even check whether a given chess board is valid. Rubik’s Cube decision problem is in NP because it is trivial to tell whether a given cube is a solution. In contrast, there is no knowledge of an efficient algorithm that can solve this problem. Source: hackerdashery.

Do P and NP are actually the same? If Yes, it means that all the problems in NP can be efficiently solved even though we still haven’t found the mysterious algorithms that achieve that. Otherwise, there are problems in NP that are impossible to solve efficiently, and any attempt to do so would mean a complete waste of our time and efforts.

Given two positive integers n and k, decide whether n has a prime factor smaller than k.

— The Prime Factorization Decision Problem

Image for post
Image for post
RSA-2048 has 617 decimal digits (2,048 bits). It is the largest of the RSA numbers and carried the largest cash prize for its factorization, $200,000. The RSA-2048 may not be factorizable for many years to come unless considerable advances are made in integer factorization or computational power in the near future.
Image for post
Image for post
Christian Boehmer Anfinsen in his lab. He was one of the 1972 winners of the Nobel Prize in Chemistry for his efforts to study the folding of a small, hardy 100-amino-acid-long protein called ribonuclease A. The Protein Folding Problem is an NP problem.
Image for post
Image for post
Pythagoras of Crotana, J. Augustus Knapp

If T is a theorem and p is its proof, then p is a solution for the decision problem: “Is T correct?”

P equals NP may imply that proving a mathematical theorem is not fundamentally harder than verifying the correctness of its proof.

“P equals NP would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time.”

— Stephen Cook

Image for post
Image for post
Charles Darwin’s writings

“We admire Wiles’ proof of Fermat’s Last Theorem, the scientific theories of Newton, Einstein, Darwin, Watson and Crick, the design of the Golden Gate bridge and the Pyramids, and sometimes even Hercule Poirot’s and Miss Marple’s analysis of a murder, precisely because they seem to require a leap which cannot be made by everyone, let alone by a simple mechanical device”

— Avi Wigderson

“If P = NP, any human or computer would have the sort of reasoning power traditionally ascribed to deities, and this seems hard to accept.”

— Avi Wigderson

Image for post
Image for post
Mozart, c. 1781, detail from portrait by Johann Nepomuk della Croce

“If P=NP, then the world would be a profoundly different place than we usually assume it to be. Everyone who could appreciate a symphony would be Mozart.”

— Scott Aaronson

Cantor’s Paradise

Medium’s #1 Math Publication!

Eliran Natan

Written by

Creating Reactive Apps that shape Human lives, focusing on IoT and Progressive Web Experiences. I share code and experiences on theHardcoded.blog

Cantor’s Paradise

Medium’s #1 Math Publication

Eliran Natan

Written by

Creating Reactive Apps that shape Human lives, focusing on IoT and Progressive Web Experiences. I share code and experiences on theHardcoded.blog

Cantor’s Paradise

Medium’s #1 Math Publication

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store