[演算] P, NP, NPC, NP-hard

[ajnightmare (阿華田)]

P是?
  一個可以在O(n^k),k是一個常數,解出的問題

NP是?
  非決定性多項式時間(non-deterministic polynomial time)
  NP的問題是所有會回答"是"或"否"問題的集合,
  而且,當它回答"是"的時候,答案確實是"是",而且可以在多項式時間被驗證.
  當它回答"否"的時候,並沒有方法可以證明答案是不是正確的.

Nondeterministic algorithm
  一個演算法具有一個或多個路徑選擇點,每個路徑都有可能會走
  但沒任何方法知道會走哪一條

NPC是?
  假如有個問題C滿足兩個條件
  1.C屬於NP問題
  2.任何的NP問題 can be reduced to C
  定義C就是NPC的問題
  意思是C就是NP集合中最難的問題.

NP-hard是?
  假如有個問題H滿足
  一個NPC的問題 can be reduced to H.
  定義H是NP-Hard的問題
  因為H至少要跟NP中最難的問題一樣難.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.7.59
→ ajnightmare:NP我似乎只有解釋NP的問題而沒解釋本身
推 aldreamp:"任何的NP問題 can be reduced from C" 是C比較簡單嗎?
推 aldreamp:一個NPC的問題 can be reduced "from" H 寫to呢?
推 jane050177:NP: a class of problem which there exits a
→ jane050177:nondeterministic algo which running time is
→ jane050177:polynomial  in size of inputs
※ 編輯: ajnightmare     來自: 58.114.208.7         (06/18 22:23)
※ 編輯: ajnightmare     來自: 58.114.208.7         (06/19 00:24)