В.Н. Крупский

Сложность вычислений

конспект pdf. Список вопросов к экзамену: 1-20, ps.

Полугодовой спецкурс, 2005 г.
Первая лекция -- 7 сентября в 16:20, ауд. 13-03.

• Модели вычислений.
• Классы P и P/Poly.
• Класс NP.
• Класс BPP.
• Полиномиальная иерархия.
• Класс PSPACE.