Close Help Print
 Course module: 201300042
 201300042Limits to Computing
 Course info
Course module201300042
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact persondr. B. Manthey
E-mailb.manthey@utwente.nl
Lecturer(s)
 Contactperson for the course dr. B. Manthey Examinator dr. B. Manthey
Starting block
 1A
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Learning goals
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } Knowing different models of computation, and being able to explain how they are equivalent Knowledge of standard undecidable problems, and methods for proving undecidability (e.g Rice's Theorem) A solid understanding of the basic notions in complexity theory (time and space complexity, hardness and completeness, different types of reductions) Being able to give simple reductions, to prove hardness of problems for various complexity classes Knowledge of the most important complexity classes (P, NP, coNP, PSPACE, L, NL), typical complete problems for them, and relations between them A feeling for the implications of complexity on practical problems
Content
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } A central topic in computer science and mathematics is the study of computation problems, such as: Compute a shortest path in a network Decide whether a given set of numbers can be partitioned into two parts with equal sum Given a logic formula, decide whether the variables can be set so that the formula is true Given a position in a two player board game, decide who wins (under perfect play) Decide whether two given programs return the same output on every input Intuitively, such problems come in varying degrees of hardness; some seem more easily solvable algorithmically than others. Some problems are not solvable at all by algorithmic means. The central question of this course is: how can we formally quantify the hardness of computational problems, and give evidence that certain problems are harder than others? This leads to the following questions: How can we define algorithmic computation? Are there any limits to what is computable at all? What are suitable measures for the performance of an algorithm? What are the most important complexity classes, how are they related, and what are the typical hardest problems in each class? To answer these questions, we introduce Turing Machines as a central model of computation. This is motivated by relating it to other (more familiar) computation models, and showing that essentially they all have the same computing power. First, we will study problems that cannot be computed at all on any computer. Secondly, we will introduce performance measures based on running time and memory usage (space), and introduce the classes of problems that can be solved in (nondeterministic) polynomial time and space, respectively. Reductions are introduced as a method of proving that a problem is among the hardest in its class.
Assumed previous knowledge
 a basic knowledge of algorithms, discrete mathematics (graph theory) and logic is required, such as included in any computer science or mathematics bachelor study.
 PARTICIPATING STUDY
 M-BIT
 PARTICIPATING STUDY
 M-TEL
 PARTICIPATING STUDY
 M-AM
 PARTICIPATING STUDY
 M-CSC
Required materials
-
Recommended materials
 Handouts
Instructional modes
 Lecture Tutorial
Tests
 Written exam/homework
 Close Help Print