Computational Complexity

Submitted by admin on Fri, 18/03/2016 - 14:47
Course Type: 
Core Course
ID: 
Μ104
ECTS: 
8
Credits: 
4
Semester : 
Winter
Specialization: 
1st
Credit hours (lecture): 
4
Credit hours (discussion): 
0
Credit hours (lab): 
0
Webpage: 
http://eclass.uoa.gr/courses/D402/
External Instructor : 
Fotakis

Turing Machines, computability , time complexity , space complexity , complexity classes , reductions, NP-completeness, coNP, probabilistic complexity classes , the polynomial hierarchy , counting problems , #P, proof systems , pseudorandomness, one-way functions.