# 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.

Sep 28 · 11 min read

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

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

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.

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

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

“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

“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

Written by

Written by