P = NP question

\[ P \subseteq NP \subseteq EXPTIME \subseteq NEXPTIME \] \[ P \subsetneq EXPTIME \qquad NP \subsetneq NEXPTIME\]

• Questions:
  • \(P \overset{?}{=} NP\)
  • \(NP \overset{?}{=} EXPTIME\)
  • \(EXPTIME \overset{?}{=} NEXPTIME\)

Opinion: Overrated question of little use

• NP is the running time of a “non-deterministic” turing machine that can somehow make the most optimal choice.
  • Instead of enumerating the search space, it simply picks the right decision each step
• P is the running time of a “deterministic” turing machine, which is like a typical real computer.

P = NP is just asking if this magical “non-deterministic” turing machine exists.