dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 7, пп. 4-5. NP ≠ P

к Оглавлению

4.1 Обоснуем, что всегда можно построить вышеописанный алгоритм «АнтиЭдип» - AntiOed_S() для произвольного алгориттма «Эдип» и аргументов sвида:

OedSph(…, …, …, …, …)», «-», t, S, s)

4.2. Все описанные в пункте 3 действия легко реализуются при помощи некого алгоритма-генератора в отношении такого алгоритма AntiOed_S(), программный код которого был бы передан для обработки в аргументе X. Тогда легко сгенерировать текст утверждение «AntiOed_S() = 0», другие соответствующие аргументы для запуска «Эдипа» и запустить сам «Эдип», а затем выдать свой результат после того, как «Эдип» выдаст свой (если «Эдип» остановится). Можно схематически (а можно и подробно – но это бездна рутины) написать программу для соответствующего алгоритма-генератора.

4.3. В соответствии с подразделом 5.2 «Теорема о построении алгоритма, применяемого к себе» мы можем из алгоритма-генератора предыдущего пункта сделать алгоритм, который все действия, которые алгоритм-генератор исполняет в отношении программного кода, получаемого в аргументе X – будет исполнять в отношении собственного программного кода. И, таким образом, мы описали метод (алгоритм) построения алгоритма AntiOed_S().

4.4. Если кто-то реально захочет строить AntiOed_S() в соответствии с методикой диагонализации, то пусть обратит внимание, что сначала надо построить алгоритм-генератор с одним аргуменом X. В этом алгоритме-генераторе потребуется задать в соответствующих переменных нужное S, программный код нужного «Эдипа» и программный код «Сфинкса». А уже в отношении этого алгоритма-генератора провести процедуру диагонализации относительно аргумента X. И нужный AntiOed_S() будет построен. Собственно, в названии алгоритма AntiOed_S() отражено и то, что он построен в отношении алгоритма «Эдип» и то, что работа данного «Эдипа» рассматривается тогда, когда числовая часть аргумента размера у него равна S.

4.5. Достаточно очевидно, что алгоритм «Эдип» с аргументами размера S, s не может доказать AntiOed_S() = 0? Если s корректный (s = s1(S)), то AntiOed_S() построен так, чтобы опровергнуть доказательство «Эдипа». Если же s не корректный, то базовый алгоритм проверки у задачи «Сфинкс» по построению должен возвращать 0 (Ноль) – о некорректности доказательства при подобном некорректном аргументе.

5. Перейдём к реализации плана, намеченного в пункте 1.2.

Нам надо, чтобы алгоритм проверки «Сфинкс» сообщал о произвольном алгоритме-решении «Эдип» то, что этот алгоритм «Эдип» (с аргументами размера S и s=s1(S)) не может доказать теорему о результате работы алгоритма «АтниЭдип» (построенным для заданного S). Разумеется, сообщать об алгоритме «Эдип» алгоритм «Сфинкс» будет в том случае, если переданный программный код – это программный код алгоритма, а не какая-то абракодабра.

5.1. Воспользуемся формулой из пункта 2.1 подраздела 6 «Задачи Кука и авторизуемые задачи из класса NP», добавив аргументы размера:

Sph(«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)», t, S, s, y)

Как видим, алгоритм «Сфинкс» получает в первом аргументе программный код алгоритма «Эдип» (произвольного, вообще говоря).

5.2. Если же в аргументе долга вместо корректного алгоритма с подставленным аргументом долга «объективно» передана какая-то абракодабра, то работа Сфинкса сводится к работе базового алгоритма проверки (с аргументом долга «объективно»). И именно результат базовой проверки тогда «Сфинкс» и вернёт в качестве своего результата.

5.3. Если же значение аргумента долга является подходящим под шаблон формулы пункта 5.1, то «Сфинкс» генерирует текст теоремы про результат работы алгоритма «АнтиЭдип», разобранной в подпунктах пункта 3 данного раздела. Алгоритм генерации схематически изложен в пунктах 4 текущего раздела. При этом потребуется использовать значение аргумента S (но не аргумента s – что существенно).

5.4. Сгенерированный текст теоремы сравнивается с тем значением, которое передано в аргументе t. Если тексты не совпадают, то работа алгоритма «Сфинкс» снова сводится к базовому алгоритму проверки – как и в пункте 5.2.

Если же тексты совпадают, то «Сфинкс» возвращает 0 – независимо ни от значения аргумента s, ни от значения аргумента y.

Тут имеется занятный момент отличия от модели машины Тьюринга – в отношении переменной s: она практически никак не используется в работе по «персональной подсказке». И не должна тормозить работу по выдаче «персональной подсказки», а она и не тормозит даже при обращении к «Сфинксу» из «Эдипа», если аргумент s передаётся «по ссылке». В реальном мире программа именно так и будет построена. И, кстати, этот нюанс учтён в способе обращения к «Сфинксу»:

Sph(«Oed(«Sph(…, …, …, …, …)», «-», …, …, …)», t, S, s, y)

Как видим, в значение аргумента долга переменная s не «встроена» и поэтому не становится частью существенной для анализа информации. В некотором смысле аргумент s становится таким же, как и аргумент y здесь – ни на что не влияющим. Впрочем, даже в классических задачах из NP аргумент y не влияет на время работы алгоритма проверки – как только размер аргумента |y| превосходит некий полином от размера аргумента |x|.

Такой ответ «Сфинкса» будет совершенно правильным, потому что если значение аргумента s не соответствует значению аргумента S (если ss1(S)), то такое сочетание аргументов отвергается и нет никакого доказательства для y, которое могло бы это исправить. Если же аргументы S, s соответствуют друг другу, то «Эдип» не в состоянии найти никакого корректного доказательства для теоремы:

AntiOed_S() = 0

5.5. Разберём теперь время ответа «Сфинкса» при таком обращении к нему:

SphOedSph(…, …, …, …, …)», «-», …, …, …)», «AntiOed_S() = 0», S, s, y) – при этом результат работы известен – 0 (Ноль).

Как видно из подпунктов пункта 4 данного раздела, генерация текста теоремы «AntiOed_S() = 0» и выдача результата 0 потребует от «Сфинкса» полиномиального количества шагов от вот чего: От размера аргумента долга OedSph(…, …, …, …, …)», «-», …, …, …)»|, от размера аргумента |S| (от количества десятичных цифр в десятичной записи S)  и больше ни от чего. Размер теоремы не имеет значения – она же всё равно генерируется и сравнивается затем с тем, что передано в аргументе t.

Размер аргумента долга в данном случае полиномиально зависит от размеров программных текстов Sph(…, …, …, …, …) и Oed(…, …, …, …, …). Но они фиксированы для разбираемых нами подзадач (в отношении заданных «Сфинкса» и «Эдипа») общей задачи. И, таким образом, время работы «Сфинкса» в интересующем нас случае будет ограничено полиномом от размера |S|. То есть, время работы «Сфинкса» в интересующем нас случае не будет превышать некоторого v*|S|^u, где v, u – фиксированные числа.

5.6. Таким образом, мы выполнили план из пункта 1.2: «Сфинкс» выдаёт «персональную подсказку» про алгоритм «Эдип». «Персональная подсказка» - 0 (Ноль), то есть, корректный «Эдип» должен вернуть 0 (Ноль) – «Не могу найти доказательство для утверждения AntiOed_S() = 0».

Выдаётся «персональная подсказка» алгоритмом «Сфинкс» за время, полиномиальное относительно |S| (если зафиксировать размеры «Сфинкса» и «Эдипа»). В то же время «общий» ограничивающий алгоритм – полином относительно размера |s|.

Соотношение между |S| и |s| - как между линейной зависимостью и экспонентой. И, значит, любые полиномы на их базе будут неполиномиально сильно отличаться между собой – полином на базе |S| будет неполиномиально меньше полинома на базе |s|.


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments