Introduction to Complexity and Computability
Resource history | v1 (current) | created by jjones
Details
Introduction to Complexity and Computability
see v1 | created by jjones | Add resource "NTIN090 - Introduction to Complexity and Computability"
- Title
- Introduction to Complexity and Computability
- Type
- Course
- Created
- no value
- 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.
- Link
- http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index-en.html
- Identifier
- no value
authors
This resource has no history of related authors.