CS-524 / 4 credits

Teacher: Göös Mika Tapani

Language: English

## Summary

In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation. This course advances the students knowledge of computational complexity, and develop an understanding of fundamental open questions.

## Keywords

theoretical computer science

computational complexity

## Recommended courses

Theory of computation (CS-251)

Algorithms (CS-250)

## Learning Outcomes

By the end of the course, the student must be able to:

• Demonstrate an understanding of computational complexity and the P vs NP problem
• Formalize and analyze abstractions of complex scenarios/problems
• Express a good understanding of different concepts of proofs
• Prove statements that are similar to those taught in the course
• Use and understand the role of randomness in computation
• Explain recent exciting developments in theoretical computer science
• Compare different models of computation

## Transversal skills

• Demonstrate the capacity for critical thinking
• Summarize an article or a technical report.

## Teaching methods

Lecturing and exercises

## Expected student activities

Actively attending lectures and exercise sessions.  Also homeworks and exam.

## Supervision

 Office hours Yes Assistants Yes Forum Yes

No

## Bibliography

Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press.

Stasys Jukna: Boolean Function Complexity, Springer

## In the programs

• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: During the semester (winter session)
• Subject examined: Computational complexity
• Lecture: 3 Hour(s) per week x 14 weeks
• Exercises: 1 Hour(s) per week x 14 weeks

## Reference week

 Mo Tu We Th Fr 8-9 9-10 INR113 10-11 INM10 11-12 12-13 13-14 14-15 15-16 16-17 17-18 18-19 19-20 20-21 21-22

Thursday, 9h - 10h: Exercise, TP INR113

Monday, 10h - 12h: Lecture INM10