Машины Тьюринга, класс NP, сертификация простоты числа, сведения, полнота задачи об ограниченной остановке, полнота задач CircuitSAT и SAT.