This course is no longer offered
20545 Computational Complexity 1
Credits: 4 advanced credits in Computer Science
Prerequisites: Students must fulfill all English requirements and take bibliographic instruction in the Library.
Required: Algorithms, Discrete Mathematics,2 Probability for Computer Science Students (or Introduction to Statistics and Probability for Science Students), Linear Algebra I
Recommended: Automata Theory and Formal Languages
The course is based on Computational Complexity, by C.H. Papadimitriou (Addison Wesley, 1994).
The course aims to provide students with in-depth knowledge of basic theoretical topics such as Turing Machines and NP-completeness. It is intended for students in the later stages of their studies.
Topics: Turing Machines basic Turing Machines, random access machine (RAM) and its equivalence with TM model; Undecidability Universal Turing Machines, the Halting Problem, Rices theorem; Relations between complexity classes basic complexity classes, hierarchy theorems, basic inclusion theorems; Reductions and completeness NP-completeness, P-completeness, Cooks theorem; NP-complete problems satisfiability, graph problems, number theory problems, set theory problems, pseudo-polynomial algorithms, strong NP-completeness; Co-NP and function problems coNP, primality testing, computation problems, total functions; Probabilistic algorithms symbolic computations, random walks and 2-SAT, algorithms for primality, RP, PP, BPP, circuit models; Cryptography public keys and RSA; Approximability vertex cover and satisfiability; Parallel Computation parallel computation, NC.
1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.
2or the previous version of Discrete Mathematics (20276), which is no longer offered.