P and NP

• P: solvable in polynomial time (\(O(n^k))\)
  
• NP-Complete, can only solve in exponential time (\(2^O(n^k)\))
  Solving one gives the solution to every other one
• Intuitive definition of P and NP: Source: hackerdashery
  NP: all problems that you can check for a solution in polynomial time! e.g. sudoku
  P: all problems that you can solve in polynomial time! e.g. multiplication
  Chess is above NP since even if we were given an answer to the best move with a certain setup, there's no way to verify it "fast"; But with sudoku, we can check if an answer is correct "fast"
• Three choices for NP:
  • Use a known algorithm accepting the long runtime
  • Use P algorithm for approximating solution
  • Constrain problem to P
• NP: can be checked in polynomial time
• If an NP-Complete problem is solved, everything in NP is solved
  \(\Longrightarrow\) NP-Complete is at least as hard as everything else in NP

Decision Problems

• e.g.:
  \(\begin{array}{l} {\text { 1. Given a weighted graph, what is the minimum length cycle that visits each node }} \\ {\text { exactly once? (If no such cycle exists, the minimum length is defined to be } \infty )\\ {\text { 2. Given a weighted graph and an integer } K, \text { is there a cycle that visits each node exactly }} \\ {\text { once, with weight at most } K ?}\end{array}\)
• If 1 can be solved, the answer can be used to solve 2

Reduction