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

Материал из Викиконспекты
Перейти к: навигация, поиск
(ToDo)
(нет различий)

Версия 20:07, 7 мая 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] переходов МТ обязательно должна приходить в «допускающую» конфигурацию, если такая цепочка переходов есть.