Complexity Theory

Deterministic vs Nondeterministic

• Deterministic Machine
  • Takes a series of sequential steps to arrive at a solution
  • Would have to do an exhaustive search to find a solution
  • A Turing machine
• Nondeterministic Machine
  • Makes arbitrary decisions
  • Whenever there is a choice it always makes the right one
  • Like a Turing machine that can flip coins
• Only deterministic machines exist

Problem Types

Polynomial (P)

• Class of problems that can run in polynomial time on a deterministic machine

Nondeterministic Polynomial (NP)

• Class of problems that can run in polynomial time on a deterministic machine
• But the solution can be verified in polynomial time on a deterministic machine
• Example problems
  • Public key encryption
  • Solving Soduku
• All P problems exist inside of NP

NP Hard

• We do not know if there are deterministic algorithms or not
• Example
  • Halting problem
  • Traveling Salesman

NP Complete

• If a problem is both NP and NP-Hard