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

Foundations of computability and complexity theory


Курс дает ответы на такие вопросы: Что такое алгоритм? Что такое эффективный алгоритм? Что такое доказательство? Как доказать, что нет алгоритма, который решит данную задачу? Как доказать, что что-то нельзя доказать? Как понять, что нет эффективного алгоритма для данной задачи? Что такое сложность объекта? Из курса можно узнать, что такое вычислимые функции, арифметическая иерархия, колмогоровская сложность, классы P, NP, PSPACE и пр., полиномиальная иерархия, схемная сложность, сложность с ограничением по памяти и многие другие интересные вещи.

Course Offerings

Semester Branch
autumn 2014 Saint Petersburg
autumn 2012 Saint Petersburg