Автоматы, 3 семестр

Полный список вопросов:

Вопросы на 'E':

Определение Машины Тьюринга и классов R и RE. Формулировка Halting Problem.
Классы сложности P, NP, NP-complete, co-NP, PSPACE, EXP. Взаимосвязь классов.
Формулировка задач SAT, 3-CNF-SAT, TQBF, ILP.
Умение понять, что перед вами формула арифметики Пресбургера (PrA). (в прошлом году был человек, долго размышлявший над формулой \exists x (y = 2x). Это было впечатляюще!).
Формулировка теоремы Пресбургера об элиминации кванторов.
Определение NFA/DFA; языка, распознаваемого NFA. Оценка числа состояний для языков, распознающих пересечение, объединение, дополнение языков, распознаваемых NFA/DFA.
Как проверить, что язык, распознаваемый NFA не будет пустым?
Формулировка задачи Intersection non-emptiness problem (for NFA).
Определение 2-регулярноcти некоторого подмножества IN^n.