過去の講義で何度も使った、Garey & Johnson: ``Computers and Intractability: A Guide to the Theory of NP-Completeness"
卒業研究でロボットやプログラムを作りましたというのは結構なことだが、大学で情報科学を勉強したというのであれば、NP完全の理論くらいは理解して卒業して欲しい。実際、就職試験の問題としても最もよく出題されているのではないか。私も、毎年限られた時間で、NP完全理論の概要を講義している。
昨日の講義では、NP完全理論の一般論を60分、確率的推論がNP困難問題である証明を30分で説明した。