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