Computational Complexity

1.00 credits · Undergraduate

Order of Growth notation, time and space complexities of DTMs and NDTMs, intractability, basic complexity classes, P=NP?, reducibility and completeness, NP-completeness, Cook's theorem, hierarchy results, circuit complexity, probabilistic algorithms, models for parallel computation.