Introduction to Complexity and Computability


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

Description

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.

Relations

is about Theory of computation

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

Currently, no authors are attached.

follows Introduction to the Theory of Computation, 3rd edition

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

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...


Edit resource 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
janarez
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.
jjones
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