Просмотр исходного текста страницы Обсуждение:Теорема Сэвича. Совпадение классов NPS и PS

== 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>p \in \mathrm{P}</tex> несет в себе несколько иной смысл, нежели предполагается в местных определениях.

Второй предложение в доказательстве второй теоремы — без комментариев…

[[Участник:Kirelagin|Кирилл Елагин]] 12:59, 3 июня 2012 (GST)


Да блин, вы чё, издеваетесь?? Во-первых, штопор, прежде чем использовать, ввести надо. Во-вторых, штопор — это переход за один шаг, а не за ноль, между прочим какбэ! [[Участник:Kirelagin|Кирилл Елагин]] 13:12, 3 июня 2012 (GST)