Eli5: what are P and NP problems and how we are using it in real life?
In: Mathematics
# ELI5 Answer
P is the class of problems that are “easy” to solve. NP is the class of problems where solutions are “easy” to verify.
Cryptography, Sudoku, finding efficient routes and paths for driving or flights, determining if a single move in Magic the Gathering is legal (known to be coNP-hard) are all in view of these kinds of problems, and they’re known to lie in some classes, and whether or not they lie in certain other classes is an open question and of great interest.
# Technical Answer
P stands for “Polynomial Time,” and NP stands for “Non-deterministic Polynomial Time.”
They refer to classes of decision problems—they are what you call complexity classes, in that they classify problems based on how complex they are, how much computational resources (either time or space) they take. Decision problems are problems that have a binary yes-or-no answer. “Does this boolean formula have a satisfying assignment?” “Is this graph 3-colorable?” “Does this Turing machine halt?” (this one is in a famous complexity class called RE) Etc.
P are those problems (formalized as *languages*, the set of all strings that represent a given instance of the problem, where the answer is “yes”) that are decidable in polynomial time, meaning there exists an algorithm that can answer the question in time that’s polynomial in the size of the input. I.e., the runtime of the algorithm scales polynomially with the size of the input. More on why polynomial is important in a minute.
NP are those problems that are decidable by a non-deterministic Turing machine in polynomial time. Or more colloquially, they are problems where given a candidate solution to the problem, you can verify whether or not the solution is correct in polynomial time.
A famous example is integer factorization (and similar problems like the discrete logarithm problem, or the elliptic curve discrete logarithm), one of the problems that underlies the heart of modern cryptography and therefore all digital communications. Given a composite number n, it is not known if there is a polynomial time algorithm to decompose it into its prime factors. However, given a propposed factorization of n, it’s easy to verify if those factors do indeed multiply out to n. In other words, it’s known to be in NP, but we’re uncertain if it’s in P.
Why is polynomial significant? Because it’s generally considered “easy” (there are exceptions to this, but that is the ELI5 simplification). If as the input size of the problem grows (bigger graph, bigger boolean formula, bigger sudoku puzzle, bigger chess board), the time it takes to find the answer only grows polynomially, well, that’s often tractable, and we can scale our solvers with relative ease. But if not, we have a problem: as the problem size grows, the resource usage blows up and we don’t have enough time, enough space in the universe to solve it even for relatively small inputs.
Let’s assume for a second P ≠ NP. That means there are some problems that truly are fundamentally “hard” to solve, but when given an alleged answer to an instance of the problem, you can quickly and efficiently verify.
If it could be proven P = NP, that could have disastarous consequences. Assuming the proof was constructive (someone came up with a polynomial-time solver for some NP-complete problem), you would instantly have a polynomial-time reduction of all problems in NP to a problem in P, collapsing the two and making all NP problems (all sorts of interesting verification problems) solvable in polynomial time. Assuming the polynomial wasn’t too large, that would upend cryptography.
Latest Answers