Definition. NTIME(t(n)) [ntime-tn]

NTIME(𝑡(𝑛))={language𝐿:∃NTM𝑀thatdecides𝐿in time𝑂(𝑡(𝑛))}

NP (complexity class) [cpsc/np]

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

Obvious: P ⊂\subset NP

Example. 3colormap ∈\in NP

Let’s prove that 3colormap is in NP.

Proof: Design a nondeterministic Turing machine to decide 3colormap in polynomial time.

  • Iterate through vertices
  • Nondetermistically pick a color for each vertex (a “lucky guess”)
  • Check all pairs of neighbors to see if they are the same color
  • If so reject, otherwise accept