Computational problems whose solutions can be verified quickly but are believed to require exponential time to solve.