Hand someone a completed sudoku grid and ask them to check it's correct, and they can do it in a couple of minutes by scanning rows, columns and boxes. Hand them a blank grid and ask them to solve it, and there's no known shortcut — every fast method anyone has ever found eventually falls back on some amount of trial and error that grows explosively as the grid gets bigger. That gap, between how fast a solution can be checked and how fast one can be found, is the entire content of the most famous open problem in computer science: is P equal to NP?
Two different kinds of "fast"
P is the set of problems a computer can solve quickly — in a time that grows manageably as the problem gets bigger. NP is the set of problems where, if someone hands you a proposed solution, you can verify it's correct quickly, even if finding that solution in the first place might take far longer. Every problem in P is automatically in NP, because if you can solve something quickly, you can obviously also check a proposed answer quickly. The open question is whether the reverse is true: does the ability to verify a solution fast always mean a fast way to find one exists, even if nobody has found it yet?
Why one problem's difficulty stands in for thousands
In 1971, Stephen Cook proved something unexpected: a specific logic problem called Boolean satisfiability is "NP-complete," meaning every other problem in NP can be systematically translated into it. If anyone ever found a fast algorithm for satisfiability, that algorithm — combined with the translation — would instantly solve every problem in NP quickly, collapsing the distinction between P and NP entirely. Richard Karp extended the result the following year, showing dozens of everyday problems — scheduling, route planning, packing, graph colouring, and yes, sudoku — are all NP-complete too, secretly the same problem wearing different clothes. Solve any one of them fast, in general, and you've solved them all.
What we're still unsure about
Most researchers strongly suspect P does not equal NP — that a genuine gap exists between checking and solving, and it isn't just a failure of imagination. That suspicion rests on decades of nobody finding a fast general algorithm despite enormous effort, not on a completed proof. The Clay Mathematics Institute lists it as one of seven Millennium Prize problems, with a one-million-dollar reward for a correct proof in either direction, and at least one high-profile attempted proof — Vinay Deolalikar's 2010 paper — drew intense public scrutiny before the mathematical community found a fatal flaw in it. The honest state of the field is that P vs NP remains genuinely open, which is a different claim than "everyone knows the answer and just hasn't written it down yet."
This sits inside NP-Completeness & Reducibility, one of eight topics in Algorithms, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.