#дневниклекций
Сегодня изучали разные сложностные классы, связанные с затраченным временем:
- Измерение времени работы машины, решающей данную задачу
- Асимптотики o, O, Θ, Ω, ω
- Классы DTIME(T(n))
- Временные сложностные классы P, QP, SUBEXP, E, EXP, EEXP и т.д. Теорема об иерархии по времени (б/д, применительно к указанным классам)
- Примеры задач из класса P: разные конкретные примеры и неконструктивные доказательства через миноры графов и теорему Робертсона-Сеймура
- Примеры задач из класса QP: перебор нужного размера и доминирующие множества в турнирах
- Примеры задач из E и EXP: перебор и поиск выигрышных стратегий
- Недетерминированные машины Тьюринга
- Два определения класса NP: через верификаторы и через НМТ. Их эквивалентность. Другие классы NTIME(T(n)), NEXP
- Класс coNP и примеры задач из пересечения NP и coNP: FACTORING и игры специального вида