Applications and Time Complexity Analysis

• 說明下列方法的特性。
  • (適用於這類型方法的問題(每類至少舉出2個例子與解法)？Time Complexity O(?).)
  • (20%)Greedy Method
  • (20%)Dynamic Programming
  • (20%)Branch-and-Bound
• P, NP, NP-C
  • (20%)什麼是Class-P ? Class-NP ?NP-C問題？它們之間的關係為何(用圖表示)？
  • (10%)說明如何證明一個問題是NP-C問題？
  • (10%)如何面對一個NP-C問題？可能有哪些方法？請舉例說明。