In order to illustrate an introduction on computational complexity, I am trying to find examples of real-life problems for every one of the main complexity classes: $P$, $NP$, $EXP$, $R$ and undecidable.
The idea is to have at least one problem per class that is easy to explain, and that is not in the previous class (assuming $P ≠ NP$ and $NP ≠ EXP$).
So far, I have:
- $P$: cycle detection in a graph
- $NP$: Travelling Salesman or Tetris
- $EXP$: Generalized Chess or Go
- $R$: ???
- undecidable: Halting problem
Any idea for $R$?
