Обсуждение:Теорема Карпа — Липтона — различия между версиями
Grechko (обсуждение | вклад) (→Доказательство) |
(→Доказательство: magic scheme trouble) |
||
| Строка 5: | Строка 5: | ||
:: Что-то я такого не припоминаю, но повторить надо в любом случае. [[Участник:Kirelagin|Кирилл Елагин]] 15:11, 30 апреля 2012 (GST) | :: Что-то я такого не припоминаю, но повторить надо в любом случае. [[Участник:Kirelagin|Кирилл Елагин]] 15:11, 30 апреля 2012 (GST) | ||
::: Добавил например --[[Участник:Grechko|Grechko]] 19:58, 30 апреля 2012 (GST) | ::: Добавил например --[[Участник:Grechko|Grechko]] 19:58, 30 апреля 2012 (GST) | ||
| + | |||
| + | Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из <tex>P</tex>, а утверждается в конце леммы, что мы получили программу из <tex>P</tex>, соответствующую схему для любой длины входа? Возможное решение: использовать схему как подсказку, тогда получим программу из <tex>P/poly</tex> (вроде бы то что хотели). | ||
Версия 20:49, 2 июня 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)
Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из , а утверждается в конце леммы, что мы получили программу из , соответствующую схему для любой длины входа? Возможное решение: использовать схему как подсказку, тогда получим программу из (вроде бы то что хотели).
