| ▲ | emil-lp an hour ago | |
If a problem is in NP, which all NP-complete problems are, then the yes-instances of the problem have "small" solutions that can be verified efficiently. Take sudoku. If I give you a difficult board, and also the solution, it is easy to verify that it is correct. Small efficient certificates do not exist for PSPACE-complete problems. Indeed for Sokoban, some instances require exponentially long sequences of pushes to solve. | ||