Вопросы к экзамену
Сложность алгоритма. Временная и емкостная сложность. Сложность в среднем и сложность в худшем случае. Асимптотические оценки сложности. Сложность задачи. Теорема Блюма об ускорении (без доказательства). Классы сложности.
Машины Тьюринга (детерминированные, одноленточные и многоленточные). Классы DTIME(f(n)). Теорема об универсальной МТ. Теорема о моделировании многоленточных МТ с помощью одноленточной МТ. Классы P (PTIME),EXPTIME. Теорема об ускорении. Симулятор с ограничением по времени. Теорема об иерархии.
Недетерминированные машины Тьюринга. НМТ для задачи о разбиении. Теорема о моделировании НМТ с помощью ДМТ. Классы NP (NPTIME) и co-NP. Определение класса NP через сертификаты. Теорема об эквивалентности двух определений класса NP. Теорема Левина (без доказательства).
Классы по емкостной сложности (PSPACE, NPSPACE). Теоремы о соотношении классов PSPACE, NPSPACE и NPTIME (без доказательства, но указать, из чего они следуют).
Полиномиальная сводимость по Куку и по Карпу. NP-трудные и NP-полные задачи. NP-полнота задач SAT, 3-SAT и CLIQUE.
Вероятностные алгоритмы. Способы задания (online, offline). Классификация (типа Монте-Карло, типа Лас-Вегас). Классы RP и co-RP. Теорема об эквивалентности определений класса RP. Класс BPP, простое и обобщенное определение. Класс ZPP, теорема о соотношении ZPP, RP и co-RP. Вероятностный алгоритм для решения задачи о равенстве матриц.
Криптосистемы с открытым ключом. Стойкость криптосистемы. Условия существования стойких крипосистем с открытым ключом. Односторонние функции. Псевдослучайные генераторы, их связь с односторонними функциями (без доказательства) и стойкими криптосистемами с секретным ключом (шифр Вернама). Интерактивные доказательства, класс IP. Примеры интерактивных доказательств на примере задач изоморфизма и неизоморфизма графов. Теорема о соотношении IP и PSPACE (без доказательства).
Замечание. Если возле названия теоремы не указано «без доказательства», то ее необходимо доказывать — в том объеме, как я это делал на лекциях. Если указан какой-либо термин или название класса, то необходимо дать определения и перечислить известные свойства.
Литература