Decidability and the P vs NP Problem

A decision problem is a question that always has the answer: yes or no, true or false, accept or reject (never a range of possible outputs, a number, or a list). A decision problem is essentially a task that decides whether its input possesses some particular property, and outputs "true" or "false" accordingly. Computer scientists often describe it as a function whose only possible output values are 0 and 1.

Everyday examples of decision problems include: is this number prime? Is this string a palindrome? Is this graph connected? Does this Sudoku grid have a solution?

Decidability is about whether a guaranteed algorithm exists for a problem and not about how fast that algorithm is. A decidable problem is one for which a solution can be found in a finite amount of time, meaning an algorithm exists that always provides a correct answer, no exceptions, and no infinite loops.

This is a strong requirement, and it's a separate question from efficiency, an algorithm can be correct and decidable while still being wildly slow. Decidability is the baseline; P and NP describe finer distinctions on top of it, about how efficiently decidable problems can actually be handled.

The most famous counterexample is the Halting Problem: whether there exists a general algorithm that can look at any given computer program plus its input and correctly determine, for every case, whether that program will eventually halt or run forever. In the 1930s, Alan Turing proved no such algorithm can exist. Interestingly, the Halting Problem is only "half decidable". The impossibility is specifically about detecting in advance, with certainty, that a program will run forever.

Class P ("polynomial time") contains every decision problem solvable by an algorithm whose running time grows only polynomially with the size of the input. Problems in P are the ones computer scientists consider genuinely tractable at scale (sorting a list, searching a table, basic arithmetic, checking connectivity in a graph).

Class NP ("nondeterministic polynomial time") contains every decision problem where, if someone hands you a proposed "yes" answer along with supporting evidence, you can verify that evidence is correct in polynomial time even if you have no idea how to have found that evidence yourself. The class of questions where an answer can be verified in polynomial time is NP. For example, given a filled-in Sudoku grid of size n×n, checking whether it's a valid solution is fast (just scan the rows, columns, and boxes) but nobody currently knows a fast way to solve an arbitrary blank Sudoku puzzle from scratch. That makes generalized Sudoku a member of NP, while its status in P remains unresolved.

Every problem in P is automatically also in NP; if you can solve something quickly, you can trivially "verify" a solution quickly too, just by re-solving it.

The question asks: is verifying always just as hard as solving, or can verifying be easier? Most computer scientists strongly think that the answer is no, that P ≠ NP, meaning there really are problems where checking a solution is fast but finding one from scratch is not, no matter how cleverly you write the algorithm. A science writer raised a nice analogy: NP problems are like riddles, it can be hard to think up the answer to a riddle, but once you hear it, it's immediately obvious it's correct. P vs NP asks whether that gap between "coming up with it" and "recognizing it" is a real one, or whether it's just an illusion caused by us not yet having found the right algorithms.

The problem's formal roots go back further away: in a 1956 letter to John von Neumann, Kurt Gödel effectively wondered whether a certain hard problem could be solved efficiently. Stephen Cook then gave it its precise modern statement in a landmark 1971 paper, "The Complexity of Theorem Proving Procedures," which is generally treated as the formal birth of the P vs NP problem in computer science.

It's one of seven Millennium Prize Problems named by the Clay Mathematics Institute in May 2000, each carrying a $1,000,000 prize for the first correct, peer-reviewed solution. So, resolving it earns you $1,000,000. Only one (the Poincaré Conjecture) has actually been solved to date, however the mathematician responsible, Grigori Perelman, turned down both the prize money and the Fields Medal that came with it.

It's also worth noting the prize is nothing next to the actual stakes of the problem. Because so many fields secretly depend on assumptions about how P and NP relate, a rigorously proven answer either way would have profound implications for many areas (mathematics, artificial intelligence, game theory, philosophy, economics, etc). In practice, "how much richer" probably has two very different answers depending on which way the proof goes: proving P ≠ NP (the widely expected outcome) would mostly just formally confirm what everyone already assumes and earn the prize and enormous prestige; but proving P = NP could be so disruptive to cryptography and computing that its practical value would bypass the million-dollar prize.