Обсуждение:Теорема Сэвича. Совпадение классов 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)