Definition. P and EXP [p-exp]

Definition 1. P (complexity class) [p]

P=⋃c>0TIME(nc)P = \bigcup_{c > 0}\text{TIME}\left( n^{c} \right)

Why is P a good definition for efficient computation?

  • Insensitive to model of computation: by the extended Church-Turing thesis, switching computational models “only” involves a polynomial slowdown
  • Closed under composition: can use polynomial time algorithm as a subroutine
  • In practice: algorithms usually can be improved. If we find an O(n30)O\left( n^{30} \right) time algorithm, it typically can be improved to, say, O(n5)O\left( n^{5} \right) time.

Example. 2COLORMAP

Let GG be a “map” of countries in the plane, where a coloring is valid if neighboring countries have different colors.

Question. The two color map does not work for every map. So consider it as a problem: 2COLORMAP={⟨G⟩:Ghas valid red/blue coloring}\text{2COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{has valid red/blue coloring}} \right\}. Is 2COLORMAP ∈\in P?

Answer. Yes! Start with an arbitrary country, set it to red, set their neighbors to blue, and continue. If there is a conflict, reject, if there is no conflict, accept.

It’s unknown if the three color map is in P. It’s known to be in EXP: O(3nn2)∈O(4n)O\left( {3^{n}n^{2}} \right) \in O\left( 4^{n} \right)

Definition 2. EXP [exp]

$`\text{EXP}` = \bigcup_{k > 0}\text{TIME}\left( 2^{n^{k}} \right)$

The four color map works for all maps, so 4COLORMAP={⟨G⟩:Gis a valid map}\text{4COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{is a valid map}} \right\}.