Теория сложности вычислений, занятие 1

Разнообразные алгоритмы для решения различных задач повсеместно встречаются как в науке и технике, так и в обыденной жизни. В этом курсе мы поговорим об общей дисциплине, которая занимается изучением эффективности или, если угодно, качества алгоритмов вне зависимости от их вида и происхождения.
На лекции основной упор будет сделан на наиболее общих классических идеях; при этом наше изложение будет довольно неформальным. Мы познакомимся с тьюринговой и булевой сложностью и поговорим про вопрос P vs. NP. Последующие занятия будут посвящены более современным исследованиям, включая применения основных концепций теории сложности за пределами теории алгоритмов в строгом смысле.
Предварительных знаний для понимания курса не требуется, но заинтересованные слушатели могут заранее познакомиться с популярной статьёй докладчика на эту тему: А.А.Разборов. Теория сложности в книге «Математическая составляющая».