Theory of Computational Complexity

Course Purpose
The purpose of this course is for students to obtain basic knowledge about the theory of computational complexity.
Learning Goals
Students will obtain basic knowledge of the theory of computational complexity and will acquire an understanding of the computational model, computability, and computational complexity.
Q
Topic
Session 1Guidance, basic concepts
Session 2Turing machine (1) (Definition and properties)
Session 3Turing machine (2) (Nondeterministic turing machine)
Session 4Calculate the possibility (1) (Understand the possibility)
Session 5Calculate the possibility (2) (Determine the possibility)
Session 6Computational complexity (1) (Definition of computational complexity)
Session 7Computational complexity (2) (Class P and class NP)
Session 8Computational complexity (3) (Reduction)
Session 9Computational complexity (4) (NP completeness)
Session 10Computational complexity (5) (Area amount, various calculation amount classes)
Session 11Probability algorithm
Session 12Approximation algorithm
Session 13Advanced topics (1) (Constant time algorithm, online algorithm, stream algorithm)
Session 14Advanced topics (2) (Quantum computation, zero-knowledge proofs), summary
＊＊This content is based on April 1, 2024. For the latest syllabus information and details, please check the syllabus information inquiry page provided by the university.＊＊