学部・大学院区分
Undergraduate / Graduate

理学部

時間割コード
Registration Code

0619921

科目区分
Course Category

専門科目
Specialized Courses

科目名　【日本語】
Course Title

数理解析・計算機数学特別講義Ⅰ

科目名　【英語】
Course Title

Special Course on Computational Mathematics and Computer Science I

コースナンバリングコード
Course Numbering Code

担当教員　【日本語】
Instructor

平原　秀一 ○

担当教員　【英語】
Instructor

HIRAHARA Shuichi ○

単位数
Credits

開講期・開講時間帯
Term / Day / Period

春集中その他その他
Intensive(Spring) Other Other

授業形態
Course style

講義
Lecture

学科・専攻
Department / Program

数理学科

必修・選択
Compulsory / Selected

選択

授業の目的　【日本語】
Goals of the Course(JPN)

計算量理論は、効率的な計算の限界を追求する理論であり、我々の身の回りで使われている公開鍵暗号方式などの安全性を支えている理論である。計算量理論の中心的未解決問題であるP対NP問題は、ミレニアム懸賞問題の一つであり、その解決には１００万ドルの懸賞金がかけられている。

本集中講義では、P対NP問題の重要性や正確な定式化、そしてNP完全性の理論を理解することを目標とする。

Computational complexity theory aims at understanding the limits of efficient computations, and supports the security of public-key cryptosystems. The central open question is the P versus NP question, which is one of the Millennium prize problems.

The primary purpose of this course is to understand the importance of the P versus NP question and the theory of NP-completeness.

授業の目的　【英語】
Goals of the Course

到達目標　【日本語】
Objectives of the Course(JPN))

授業終了時に、以下のことができるようになることを目標とします。
1. P対NP問題の重要性を説明できる。
2. 計算問題がNPに属することを判定できるようになる。
3. 任意のNPの問題をSATに帰着することによって、広範囲の問題を解けるようになる。

到達目標　【英語】
Objectives of the Course

授業の内容や構成
Course Content / Plan

本講義は以下の内容で構成される。
1. P対NP問題と暗号理論の関係
2. 計算量クラスP, NP
3. NP完全性の理論
4. Cook-Levinの定理
5. 対角線論法と相対化のバリア

The course consists of the following parts.
1. The P versus NP question and its relationship to cryptography
2. The complexity classes, P and NP
3. The theory of NP-completeness
4. The Cook-Levin theorem
5. Diagonalization and the relativization barrier

履修条件
Course Prerequisites

-

This course will be taught in Japanese.