Изменения

Пусть <tex>I</tex> — конфигурация <tex>M</tex>. Размер конфигурации есть <tex>rp(n)</tex>, где <tex>n</tex> — длина входа, <tex>rp</tex> — некоторый полином. Тогда выражение <tex>\exists I</tex> обозначает <tex> \exists x_0^I \, \exists x_1^I \dots \exists x_{r(n)}^I</tex>, где <tex>\{x_i^I\}</tex> — все переменные конфигурации <tex>I</tex>. Аналогично выражение <tex> \forall I</tex> обозначает <tex> \forall x_0^I \, \forall x_1^I \dots \forall x_{r(n)}^I</tex>. Всего конфигураций у ДМТ <tex>M \, 2^{O(p(n))}</tex>, где <tex>p</tex> — некоторый полином.