GSI-15-6041-J

主専攻科目

選択1単位

特論

修士1・2年

秋1期月曜3限目

工学部IB館中棟1階011講義室

情報システム学専攻

関浩之

情報システム学専攻

seki@i.nagoya-u.ac.jp

問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について説明する。まず，時間計算量と領域計算量等の概念を定義した後，NP完全性を定義する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を具体例に即して説明する。さらに，クラスco-NPとPSPACE，ランダム計算，交代計算，対話証明系についても説明する。

計算機で問題を解くときの問題の難しさを計る尺度についての体系である計算複雑さの理論の基本概念と方法論を修得する。NP完全性の還元法による証明技法を例題を通して身につける。PSPACE，BPP, IP等，その他の計算量クラスとそれらの相互関係を理解する。

問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について説明する。まず，時間計算量と領域計算量等の概念を定義した後，NP完全性を定義する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を具体例に即して説明する。さらに，クラスco-NPとPSPACE，ランダム計算，交代計算，対話証明系についても説明する。
〔計画〕
1. 導入
2. 計算量クラス
3. NP完全問題
4. co-NPとPSPACE
5. ランダム計算
6. 交代計算
7. 対話証明系
8. 総括と演習

主にスライドを用いるが，定理等の詳細な証明および練習問題を加えた講義録も配布する。
教科書は指定しない。テキスト類を授業中に配布する。
参考文献：
（関担当分参考書）
1. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, 2001.
2. M.R.Garey and D.S.Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.
3. M. Sipser: Introduction to the Theory of Computation, PWS Publishing, 1997.
4. C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
5. J.L.Balcazar, J.Diaz and J.Gabarro: Structural Complexity I, Springer, 1988.
J1. 岩間一雄：オートマトン・言語と計算理論，コロナ社，2003。
J2. 丸岡章：計算理論とオートマトン言語理論，サイエンス社, 2005。
J3. 渡辺治：計算可能性・計算複雑さ入門，近代科学社，1992。

講義において説明した理論を理解するために課題を与える。

演習課題の評価２０％，試験８０％，合計１００点満点で６０点以上を合格とする。

Advanced Lectures on Foundations of Software A

GSI-15-6041-J

Main majors

Elective1

Advanced Lecture

Master1-2

Autumn 1 semester Monday 3

SEKI Hiroyuki

Department of Computing and Software Systems

seki@i.nagoya-u.ac.jp

Basic concepts on computation such as time and space complexities are introduced and NP-completeness is defined. Then we learn reduction technique, which can compare hardness of two problems and is useful for proving that a problem is NP-complete. PSPACE and co-NP are also explained. In the latter part, some other computation models including randomized computation, alternation and interactive proof systems are explained.

Computational complexity theory provides mathematical concepts and tools for representing the computational hardness of problems. Students are expected to understand the basic definitions and methodologies of the theory such as NP-completeness, to be able to use the reduction method for proving NP-completeness through examples, and to grasp other important complexity classes such as PSPACE, BPP and IP as well as their relationships.

Basic concepts on computation such as time and space complexities are introduced and NP-completeness is defined. Then we learn reduction technique, which can compare hardness of two problems and is useful for proving that a problem is NP-complete. PSPACE and co-NP are also explained. In the latter part, some other computation models including randomized computation, alternation and interactive proof systems are explained.

[Schedule]
1. Introduction
2. Complexity Classes
3. NP-complete Problems
4. Co-NP and PSPACE
5. Randomized Computation
6. Alternation
7. Interactive Proof Systems
8. Summary and Exercise

No specific textbook is used. Slides are mainly used in a class. Handouts including formal proofs and exercises will be delivered.

References
1. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, 2001.
2. M.R.Garey and D.S.Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.
3. M. Sipser: Introduction to the Theory of Computation, PWS Publishing, 1997.
4. C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
5. J.L.Balcazar, J.Diaz and J.Gabarro: Structural Complexity I, Springer, 1988.
(To be announced in the class.)

Assignments will be given.

Examination 80% and assignment 30%. Credit is given if the total score >= 60%.