Теория сложности (старая трешовая версия)
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Лекция 1. Вводная
Начнем курс с введения понятий DTIME и DSPACE.
- DTIME(f(n)) = машина Тьюринга , где — длина входа .
- DSPACE(f(n)) = машина Тьюринга .
Аналогичным образом введем классы NSPACE и NTIME, использующие недетерминированную машину Тьюринга взамен детерминированной (в течении всего курса префикс D соответствует детерминизму, а N — недетерминизму).
Рассмотрим и докажем теоремы о емкостной и временной иерархии.
- Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций и таких, что , выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).
- Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций и таких, что , выполняется DTIME(g(n)) ≠ DTIME(f(n)).
Через понятия классов DSPACE, DTIME, NSPACE и NTIME будет дано определение многим сложностным классам, в том числе P и NP.
Класс P — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально:
- P= DTIME
В свою очередь, при разрешении языка из класса NP используется недетерминированная машина:
- NP= NTIME
Дадим определение класса NP на языке сертификатов:
- NP=NP). Поясним, что является сертификатом принадлежности языку , если существует полиномиальное отношение (верификатор) , такое что тогда и только тогда, когда принадлежит . (первое равенство доказывается в статье
Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка co-). Например, класс co-NP.
Введем в рассмотрение отношения между языками: сведение по Карпу и сведение по Куку.
- Язык сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .
- Язык сводится по Куку к , если существует разрешающая язык программа , работающая полиномиальное время от длины входа, которая может использовать разрешающую программу для языка в качестве оракула. При этом время работы не учитывается.
В дальнейшем чаще будет рассматриваться сведение по Карпу.