editor
177
правок
Изменения
ToDo
== TODO ==
* <tex>poly</tex> — это множество полиномов, поэтому вместо «<tex>p(n)-poly</tex>» надо писать «<tex>p(n) \in poly</tex>»
* Что у тебя в конспекте делает теорема о вхождении <tex>L</tex> в <tex>P</tex>?
* Думаю, что вывод надо перенести в конец статьи. Потому что иначе надо ещё туда приписать <tex>NPS</tex>, а к концу мы уже знаем, что <tex>PS = NPS</tex>.
* Мне неочевидно, почему позицию и содержание рабочей ленты можно закодировать таким количеством памяти.
* Мне неочевидно, почему за <tex>log(2^{d f(n)})</tex> переходов МТ обязательно должна приходить в «допускающую» конфигурацию, если такая цепочка переходов есть.
* <tex>poly</tex> — это множество полиномов, поэтому вместо «<tex>p(n)-poly</tex>» надо писать «<tex>p(n) \in poly</tex>»
* Что у тебя в конспекте делает теорема о вхождении <tex>L</tex> в <tex>P</tex>?
* Думаю, что вывод надо перенести в конец статьи. Потому что иначе надо ещё туда приписать <tex>NPS</tex>, а к концу мы уже знаем, что <tex>PS = NPS</tex>.
* Мне неочевидно, почему позицию и содержание рабочей ленты можно закодировать таким количеством памяти.
* Мне неочевидно, почему за <tex>log(2^{d f(n)})</tex> переходов МТ обязательно должна приходить в «допускающую» конфигурацию, если такая цепочка переходов есть.
