Introduction to Complexity and Computability

Resource | v1 | created by jjones |
Type Course
Created unavailable
Identifier unavailable


This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions. Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE. Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.


about Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals w...

follows Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak

This is a textbook on computational complexity theory. It is intended as a text for an advanced under...

follows Introduction to the Theory of Computation, 3rd edition

Gain a clear understanding of even the most complex, highly theoretical computational theory topics i...

Edit details Edit relations Attach new author Attach new topic Attach new resource
7.5 /10
useless alright awesome
from 2 reviews
Write comment Rate resource Tip: Rating is anonymous unless you also write a comment.
Resource level 3.5 /10
beginner intermediate advanced
Resource clarity 6.0 /10
hardly clear sometimes unclear perfectly clear
Reviewer's background 3.5 /10
none basics intermediate advanced expert
Comments 2
0 0

6 rating 4 level 5 clarity 4 user's background

The accompanying text is great (only in Czech, though).
Slides are sometimes not enough.
0 0

9 rating 3 level 7 clarity 3 user's background

Comprehensive, from basics to advanced topics
The greatest material is currently only in Czech language
I have studied this course and it was my favorite thanks to the (Czech) lecture notes