3. Introduction of computation complexity

19th, Sept.

  • Reference: computers and intractability
  • Reference: UCI lecture

3.1. Compare pros and cons of different algorithm

  • Experiment? Need to run in the same environment
  • Complexity analysis. Independent from environment
  • Scale examples:
    • binary tree search (depth = n): equation
    • Traveling Salesman Problem (TSP, n cities): equation

3.2. Classification of problems

complexity

P,NP and NP complete

  • P: Problems that can be solved in polynomial time
  • NP: This stands for “nondeterministic polynomial time” where nondeterministic is just a fancy way of talking about guessing a solution
    • Does not stand for “non-polynomial”!!!
    • A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution)
    • equation
  • Reduction (polynomial reduction)
    • Eg: PA: sort scores of the whole class; PB: find the highest score in the class
    • PA is polynomial reducible to PB if an algorithm for solving PB efficiently (if it existed) could also be used as a subroutine to solve PA efficiently
    • equation
    • PB is at least as hard as PA
  • NP-completeness: judgment problem equation, for all other decision problems equation, we have equation, then equation is NP-completeness
    • NP completeness is the most hard problem of all NP problems
    • Any given solution to an NP-complete problem can be verified in polynomial time
    • But there is no known efficient way to locate a solution in the first place
  • What to do when facing NP-complete problem?
  • NP-complete set
  • NP hard