MTH 814 Computational Complexity

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. Lect: 3 hrs./Lab: 1 hr. Prerequisite: MTH 110 or MTH 314 Course Weight: 1.00 Billing Units: 1

There are no comments for this course.