Теория сложности (старая трешовая версия)
Лекция 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)
