Обсуждение:Теорема Карпа — Липтона

Доказательство

Переход между первым и вторым предложениями неочевиден и вообще, по-моему, это неправда. Кирилл Елагин 00:54, 30 апреля 2012 (GST)

Доказательство этого было заданием на первом тесте. Можно, конечно, и повторить. --Grechko 02:26, 30 апреля 2012 (GST)

Что-то я такого не припоминаю, но повторить надо в любом случае. Кирилл Елагин 15:11, 30 апреля 2012 (GST)

Добавил например --Grechko 19:58, 30 апреля 2012 (GST)

Пара вопросов

Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из [math]P[/math], а утверждается в конце леммы, что мы получили программу из [math]P[/math], соответствующую схему для любой длины входа? Возможное решение: использовать схему как подсказку, тогда получим программу из [math]P/poly[/math] (вроде бы то что хотели).

[math]\exists y\; \phi(x, y, z)[/math] — это не формула, потому что [math]\phi[/math] — это программа. Кажется тут что-то надо сказать про длину входа [math]\phi[/math] (она ограничена при фиксированном [math]z[/math]) и сослаться на доказательство [math]P \subset P/\mathrm{poly}[/math].