Обсуждение:Теорема Карпа — Липтона — различия между версиями
Kirelagin (обсуждение | вклад) (Доказательство) |
|||
| (не показано 6 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
| + | =Сейчас= | ||
| + | |||
| + | =Раньше= | ||
== Доказательство == | == Доказательство == | ||
Переход между первым и вторым предложениями неочевиден и вообще, по-моему, это неправда. [[Участник:Kirelagin|Кирилл Елагин]] 00:54, 30 апреля 2012 (GST) | Переход между первым и вторым предложениями неочевиден и вообще, по-моему, это неправда. [[Участник:Kirelagin|Кирилл Елагин]] 00:54, 30 апреля 2012 (GST) | ||
| + | : Доказательство этого было заданием на первом тесте. Можно, конечно, и повторить. --[[Участник:Grechko|Grechko]] 02:26, 30 апреля 2012 (GST) | ||
| + | :: Что-то я такого не припоминаю, но повторить надо в любом случае. [[Участник:Kirelagin|Кирилл Елагин]] 15:11, 30 апреля 2012 (GST) | ||
| + | ::: Добавил например --[[Участник:Grechko|Grechko]] 19:58, 30 апреля 2012 (GST) | ||
| + | |||
| + | == Пара вопросов == | ||
| + | |||
| + | Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из <tex>P</tex>, а утверждается в конце леммы, что мы получили программу из <tex>P</tex>, соответствующую схему для любой длины входа? Возможное решение: использовать схему как подсказку, тогда получим программу из <tex>P/poly</tex> (вроде бы то что хотели). | ||
| + | |||
| + | <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) | ||
Текущая версия на 02:46, 8 июня 2012
Содержание
Сейчас
Раньше
Доказательство
Переход между первым и вторым предложениями неочевиден и вообще, по-моему, это неправда. Кирилл Елагин 00:54, 30 апреля 2012 (GST)
- Доказательство этого было заданием на первом тесте. Можно, конечно, и повторить. --Grechko 02:26, 30 апреля 2012 (GST)
- Что-то я такого не припоминаю, но повторить надо в любом случае. Кирилл Елагин 15:11, 30 апреля 2012 (GST)
- Добавил например --Grechko 19:58, 30 апреля 2012 (GST)
- Что-то я такого не припоминаю, но повторить надо в любом случае. Кирилл Елагин 15:11, 30 апреля 2012 (GST)
Пара вопросов
Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из , а утверждается в конце леммы, что мы получили программу из , соответствующую схему для любой длины входа? Возможное решение: использовать схему как подсказку, тогда получим программу из (вроде бы то что хотели).
— это не формула, потому что — это программа. Кажется тут что-то надо сказать про длину входа (она ограничена при фиксированном ) и сослаться на доказательство .
Новое доказательство — новые вопросы!
Предложение «Так как задача определения выходного значения таких схем принадлежит NP, то такие схемы существуют и имеют полиномиальный размер» немного странное, поскольку я не понял, о чем оно. Но независимо от этого мне кажется, что оно ничего не доказывает.
Процесс построения схемы C_n описан, мягко говоря, мутно. Ну т.е. я вообще ничего не понял.
Кирилл Елагин 22:52, 3 июня 2012 (GST)
