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

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

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 \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