WSN20501 Computational Complexity Theory

Hiroshima University Syllabus

Japanese

Academic Year 2025Year School/Graduate School Graduate School of Advanced Science and Engineering (Master's Course) Division of Advanced Science and Engineering Informatics and Data Science Program

Lecture Code WSN20501 Subject Classification Specialized Education

Subject Name Computational Complexity Theory

Subject Name
（Katakana）コンピューテイショナル　コンプレクシティー　セオリー

Subject Name in
English Computational Complexity Theory

Instructor IWAMOTO CHUZO

Instructor
(Katakana) イワモト　チュウゾウ

Campus Higashi-Hiroshima Semester/Term 1st-Year,  Second Semester,  3Term

Days, Periods, and Classrooms (3T) Tues1-4：ENG 104

Lesson Style Lecture Lesson Style
(More Details) Face-to-face

Classroom lecture

Credits 2.0 Class Hours/Week 4 Language of Instruction E : English

Course Level 6 : Graduate Advanced

Course Area（Area） 25 : Science and Technology

Course Area（Discipline） 02 : Information Science

Eligible Students

Keywords Language theory, parallel computation, uniform family of circuits, completeness and reducibility

Special Subject for Teacher Education 　 Special Subject 　

Class Status
within Educational
Program
(Applicable only to targeted subjects for undergraduate students)
Criterion referenced
Evaluation
(Applicable only to targeted subjects for undergraduate students)

Class Objectives
/Class Outline Objective: In this series of lectures, we analyze the complexity of computational problems, and classify problems into complexity classes NC, P, and NP.

Outline: One of the most efficient methods for solving computational problems is to parallelize computations.  In this series of lectures, we focus on uniform families of circuits, which are the most fundamental model for parallel computations.  We study the complexity class NC; this is the set of problems which are efficiently computable by that model.  We also discuss P-complete and NP-complete problems, which are strongly believed not to be solved efficiently in parallel and sequential, respectively.

Class Schedule Topic: Computational Complexity Theory
  (0) Guidance (0.5 week)
  (1) Parallel complexities
      Model: Boolean Circuits
      (a) Definitions of circuits and class NC (2 weeks)
      (b) Circuits for Addition (2 weeks)
      (c) Subtraction (1 week)
      (d) Multipilication (1 week)
      (e) Division (1 week)
  (2) Sequential complexities
      Model: Turing Machines, TMs
      (a) Definitions of TMs, classes DLOG, P, and NP (2 weeks)
      (b) P-complete problems (2 weeks)
      (c) NP-complete problems (3 weeks)
  (3) Conclusions (0.5 week)

Text/Reference
Books,etc. No texts.

PC or AV used in
Class,etc.

(More Details) A blackboard.

Learning techniques to be incorporated

Suggestions on
Preparation and
Review An entry test and homeworks.

Requirements

Grading Method Grades are based on reports, homeworks, and participation attitude.

Practical Experience

Summary of Practical Experience and Class Contents based on it

Message

Other

Please fill in the class improvement questionnaire which is carried out on all classes.
Instructors will reflect on your feedback and utilize the information for improving their teaching.

Academic Year	2025Year	School/Graduate School	Graduate School of Advanced Science and Engineering (Master's Course) Division of Advanced Science and Engineering Informatics and Data Science Program
Lecture Code	WSN20501	Subject Classification	Specialized Education
Subject Name	Computational Complexity Theory
Subject Name （Katakana）	コンピューテイショナル　コンプレクシティー　セオリー
Subject Name in English	Computational Complexity Theory
Instructor	IWAMOTO CHUZO
Instructor (Katakana)	イワモト　チュウゾウ
Campus	Higashi-Hiroshima	Semester/Term	1st-Year, Second Semester, 3Term
Days, Periods, and Classrooms	(3T) Tues1-4：ENG 104
Lesson Style	Lecture	Lesson Style (More Details)	Face-to-face
Classroom lecture
Credits	2.0	Class Hours/Week	4	Language of Instruction	E : English
Course Level	6 : Graduate Advanced
Course Area（Area）	25 : Science and Technology
Course Area（Discipline）	02 : Information Science
Eligible Students
Keywords	Language theory, parallel computation, uniform family of circuits, completeness and reducibility
Special Subject for Teacher Education		Special Subject
Class Status within Educational Program (Applicable only to targeted subjects for undergraduate students)
Criterion referenced Evaluation (Applicable only to targeted subjects for undergraduate students)
Class Objectives /Class Outline	Objective: In this series of lectures, we analyze the complexity of computational problems, and classify problems into complexity classes NC, P, and NP. Outline: One of the most efficient methods for solving computational problems is to parallelize computations. In this series of lectures, we focus on uniform families of circuits, which are the most fundamental model for parallel computations. We study the complexity class NC; this is the set of problems which are efficiently computable by that model. We also discuss P-complete and NP-complete problems, which are strongly believed not to be solved efficiently in parallel and sequential, respectively.
Class Schedule	Topic: Computational Complexity Theory (0) Guidance (0.5 week) (1) Parallel complexities Model: Boolean Circuits (a) Definitions of circuits and class NC (2 weeks) (b) Circuits for Addition (2 weeks) (c) Subtraction (1 week) (d) Multipilication (1 week) (e) Division (1 week) (2) Sequential complexities Model: Turing Machines, TMs (a) Definitions of TMs, classes DLOG, P, and NP (2 weeks) (b) P-complete problems (2 weeks) (c) NP-complete problems (3 weeks) (3) Conclusions (0.5 week)
Text/Reference Books,etc.	No texts.
PC or AV used in Class,etc.
(More Details)	A blackboard.
Learning techniques to be incorporated
Suggestions on Preparation and Review	An entry test and homeworks.
Requirements
Grading Method	Grades are based on reports, homeworks, and participation attitude.
Practical Experience
Summary of Practical Experience and Class Contents based on it
Message
Other
Please fill in the class improvement questionnaire which is carried out on all classes. Instructors will reflect on your feedback and utilize the information for improving their teaching.

Back to syllabus main page