Computational Complexity
Faculteit  Science and Engineering 
Jaar  2022/23 
Vakcode  WBCS04405 
Vaknaam  Computational Complexity 
Niveau(s)  bachelor 
Voertaal  Engels 
Periode  semester I a 
ECTS  5 
Rooster  rooster.rug.nl 
Uitgebreide vaknaam  Computational Complexity  
Leerdoelen  At the end of the course, the student is able to: 1) Explain the design choices that underpin classical complexity theory (the focus on time/space resources, asymptotic worst case complexity, polynomial/exponential classes) 2) Apply the basic concepts in computation and complexity such as Turing machines, (un)decidability, time and space complexity classes 3) Prove properties concerning the various complexity classes and prove the simpler main theorems 4) Construct reductions from one problem to another for suitable examples in order to classify decision problems into complexity classes 

Omschrijving  Computational complexity aims to classify computational problems based on the amount of resources (in this course: time and space) that is required by the best algorithm to solve the problem. This field may be viewed as the mathematical study of efficient computation. It is distinct from the analysis of specific algorithms although the fields are highly related. The standard choice of computational model in this field is the Turing machine. After a brief revision of Turing machines, decidability and undecidability, we examine the main ideas and techniques including the time complexity classes P and NP, the famous unsolved (open) question of P versus NP, polynomial time reducibility, NPcompleteness of SAT and other NPcomplete problems, space complexity classes like NL and PSPACE, and the hierarchy theorems which serve to separate certain complexity classes e.g. P is a proper subset of EXPTIME. This course explores at much greater technical depth certain topics that appear in Languages and Machines (WBCS02705). 

Uren per week  
Onderwijsvorm  Hoorcollege (LC), Werkcollege (T)  
Toetsvorm 
Opdracht (AST)
(The student must submit all three of the assignments in time, and score at least 5.5 in the weighted grade. This is the average of the three assignment grades. If this weighted grade is < 5.5 then the student is eligible to take an additional (Resit) assignment. In that case, the final grade (the maximum that can be obtained is then 7.0) will be calculated using the three highest assignments grades.) 

Vaksoort  bachelor  
Coördinator  D.R.S. Ramanayake, PhD.  
Docent(en)  D.R.S. Ramanayake, PhD.  
Verplichte literatuur 


Entreevoorwaarden  Assumed prior knowledge: Proficiency with discrete mathematics (sets, functions, relations), knowledge of formal languages and automata. Ability to read and carry out mathematical proofs. An interest in the theoretical and mathematical aspects of computer science. Assumed prior knowledge from the BSc Computing Science: Discrete Structures, and Languages and Machines. 

Opmerkingen  All CS bachelor courses have limited enrollment:  CS students can always enter each course, regardless of whether the course is mandatory for them or not.  A maximum of only 20 places per course is available for nonCS students. These places are filled on a firstcomefirstserved basis, with priority given to students with a strong CSrelated background (e.g., CS exchange students, AI students, etc.). These students need to meet the course prerequisite requirements as mentioned on Ocasys. For more info about the enrollment procedure, see https://student.portal.rug.nl/infonet/studenten/fse/programmes/bsccs/general/vakintekeningprocedure#cap 

Opgenomen in 
