City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекции 9-10
Structural Complexity Theory

What: Lecture
When: Sunday, 16 November 2008, 14:30–16:00
Where: ПОМИ РАН
Slides: complexitytheory_lecture_161108.pdf

Description

IP=PSPACE. Лемма Вэлиэнта–Вазирани. PCP–theorem. Неаппроксимируемость.