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

Материал из Викиконспекты
Перейти к: навигация, поиск
(ToDo)
 
 
(не показаны 2 промежуточные версии 1 участника)
Строка 5: Строка 5:
 
* Мне неочевидно, почему позицию и содержание рабочей ленты можно закодировать таким количеством памяти.
 
* Мне неочевидно, почему позицию и содержание рабочей ленты можно закодировать таким количеством памяти.
 
* Мне неочевидно, почему за <tex>log(2^{d f(n)})</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)

Текущая версия на 20:33, 4 июня 2012

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)


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