Изменения

Пусть <tex>I</tex> — конфигурация <tex>M</tex>. Размер конфигурации есть <tex>r(n)</tex>, где <tex>n</tex> — длина входа, <tex>r</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> — некоторый полином.