[講義メモ]Computational Intractability(4/20)

TSPがNP-Hardだという話を先週していたので
P,NP,NP-completeの問題の階層についてのお話.

問題の形式としてはDecision Programを考えていた.計算理論でよく使われるやつ.
決定問題 – Wikipedia

X is easy
→ Algorithm A running in polynomial time in size of the input

NP
→ Decision problems for which we can check “yes” answer in polynomial time
  Using a certificate of necessary

Problem transformation.
二つの決定問題x, yが与えられたとき,yを使ってxを解く,みたいな話.

X \leq_p Yという記号の導入.
→ X can be solved using Algorithm for Y.
→ Problem Y can reduce to problem X

NP-complete
→ A decision problem Y is NP-complete iff
 1. It is NP.
 2. For every X in NP,  X\leq_p Y – Y can be used to solve every problem in NP.

その他のキーワード.
3-SAT,COOK,4-SAT,DHC

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です