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

TODO

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

Мне кажется, что обозначение [math]p \in \mathrm{P}[/math] несет в себе несколько иной смысл, нежели предполагается в местных определениях.

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

Кирилл Елагин 12:59, 3 июня 2012 (GST)