It asks whether every problem whose answer is easy to check is also easy to solve. If so, transport could be scheduled optimally, moving people and goods faster and more cheaply, but public-key cryptography would become impossible.
What we know
Posed in 1971: if a problem is easy to check, is it also easy to solve?
What blocks us
Several major families of proof techniques have been proven insufficient.