Изменения

Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число <tex> O(1) </tex> переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> — размер входа, и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.