Halting problem

The halting problem determine if a program can run forever or not.

while True: continue;

This problem is NP-hard: we can't verify the solution in a polynomial time.