Бюрократы, editor, Администраторы
422
правки
Изменения
→Новое доказательство — новые вопросы!: Новая тема
<tex>\exists y\; \phi(x, y, z)</tex> {{---}} это не формула, потому что <tex>\phi</tex> {{---}} это программа. Кажется тут что-то надо сказать про длину входа <tex>\phi</tex> (она ограничена при фиксированном <tex>z</tex>) и сослаться на доказательство <tex>P \subset P/\mathrm{poly}</tex>.
== Новое доказательство — новые вопросы! ==
Предложение «Так как задача определения выходного значения таких схем принадлежит NP, то такие схемы существуют и имеют полиномиальный размер» немного странное, поскольку я не понял, о чем оно. Но независимо от этого мне кажется, что оно ничего не доказывает.
Процесс построения схемы C_n описан, мягко говоря, мутно. Ну т.е. я вообще ничего не понял.
[[Участник:Kirelagin|Кирилл Елагин]] 22:52, 3 июня 2012 (GST)
