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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
=Сейчас=
 +
 +
=Раньше=
 
== Доказательство ==
 
== Доказательство ==
  
Строка 5: Строка 8:
 
:: Что-то я такого не припоминаю, но повторить надо в любом случае. [[Участник: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> (вроде бы то что хотели).
 +
 +
<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)

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

Что непонятно: в лемме говорится, что мы можем за полином вычислить соответствующую схему. Вопрос: Откуда мы возьмем в программе из [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].

Новое доказательство — новые вопросы!

Предложение «Так как задача определения выходного значения таких схем принадлежит NP, то такие схемы существуют и имеют полиномиальный размер» немного странное, поскольку я не понял, о чем оно. Но независимо от этого мне кажется, что оно ничего не доказывает.

Процесс построения схемы C_n описан, мягко говоря, мутно. Ну т.е. я вообще ничего не понял.

Кирилл Елагин 22:52, 3 июня 2012 (GST)