Black Friday 2024: 25+ Ways to Save on Online Learning

Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology Kanpur

Computational Complexity Theory

Indian Institute of Technology Kanpur and NPTEL via Swayam

Go to class Write review

This course may be unavailable.

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Grab it
In this course we study mathematical techniques that enable us to show the power and limitations of various computational models. We consider these models by putting restrictions on the resources that the model can use and study the class of problems that are solvable by these models. We also compare the various classes that are thus obtained and try to give relations between them.
INTENDED AUDIENCE :Advanced undergraduate and postgraduate studentsPREREQUISITES : Design and Analysis of Algorithms, Theory of ComputationINDUSTRIES SUPPORT :None

Syllabus

COURSE LAYOUT

Week 1:NP CompletenessWeek 2:Hierarchy Theorems, Space ComplexityWeek 3:Space Complexity (contd)Week 4:Polynomial Hierarchy
Week 5:Circuit ComplexityWeek 6:Randomized ComplexityWeek 7:Valiant Vazirani TheoremWeek 8:Toda’s Theorem, Complexity of Permanent function
Week 9:Interactive ProofsWeek 10:Interactive Proofs (contd)Week 11:Circuit Lower BoundsWeek 12:Communication Complexity, PCP Theorem

Taught by

Prof. Raghunath Tewari

Tags

Reviews

Start your review of Computational Complexity Theory

Go to class

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.