P vs. NP
  - Polynomial time solution
  - nondeterministic polynomial time
  - verifiable vs solvable.
  - What is known? P <= NP Suspected: P < NP
  - It should be somewhat surprising that this is an open
    problem. Perhaps the solution is not recognizable? Is there some
    paradox wrapped up in this? Shouldn't we be able to diagonalize
    it?


PSPACE vs NSPACE
  - known to be equal
  - known P <= NP <= PSPACe = NPSPACE