The greatest unsolved problem in computer science...

Problems that a computer can solve efficiently, where the work scales at a reasonable, deterministic pace as input grows (1:45). Examples include sorting algorithms where doubling the input roughly doubles the work — these are considered tractable and form the baseline class of "easy" problems in computational complexity theory.

Problems where a proposed solution can be verified quickly in polynomial time, but finding that solution from scratch may require exploring an astronomical number of possibilities (2:15). This asymmetry between verification and discovery is the heart of the P vs NP question and has deep implications for cryptography and optimization.

Formally defined by Stephen Cook in 1971 (1:30), the question asks whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. Despite thousands of papers and decades of research, no proof exists either way, making it one of the Clay Mathematics Institute's million-dollar Millennium Prize Problems (0:08).

The video uses prime factorization as an intuitive example of the P vs NP gap (3:00). Multiplying two primes is trivially easy, but factoring their product back into components becomes exponentially harder as numbers grow — this asymmetry is the foundation of RSA encryption and modern public-key cryptography.