165
правок
Изменения
→Лекция 1
== Лекция 1 . Вводная ==*Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]*''' и '''[[Класс DTIME|DTIME]]'''. Через эти классы будет дано определение нескольким сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]
*[[Класс co-NP]]
*[[Сведение по Карпу]]
*[[Сведение по Куку]]
== Практика 1 ==
