dmitgu (dmitgu) wrote,
dmitgu
dmitgu

7. NP ≠ P

к Оглавлению

Чтобы построить авторизуемую задачу из класса NP, которую не может решить (свести к задаче из класса P) полным образом ни один алгоритм-решение, мы поступим следующим образом:

1.1. Для произвольного алгоритма-решения «Эдип» мы построим алгоритм «АнтиЭдип», про результат работы которого «Эдип» заведомо не может доказать соответствующее утверждение.

1.2. И в нашей авторизуемой задаче «Сфинкс» из класса NP будет «персональная подсказка» для «Эдипа», в соответствии с которой корректный алгоритм-решение «Эдип» должен вернуть ноль – «не могу найти доказательство утверждения про результат работы алгоритма АнтиЭдип». Притом ограничивающий алгоритм данной «персональной подсказки» у алгоритма «Сфинкс» будет неполиномиально меньшим («Сфинкс» по «персональной подсказке» будет работать неполиномиально меньшее количество шагов), чем ограничивающий алгоритм базового алгоритма проверки («общий» ограничивающий алгоритм) задачи «Сфинкс».

1.3. И вернуть результат корректный «Эдип» должен будет полиномиально быстро по меркам времени получения подсказки, что должно позволить неким другим алгоритмам найти в рамках допустимого размера доказательство о результате работы «АнтиЭдипа», которое не нашёл (и не мог найти) «Эдип».

2.1. За основу алгоритма проверки возьмём теорию на базе Пеано, способную представлять произвольные алгоритмы. Базовый алгоритм проверки при допустимом размере доказательства проверяет стандартным алгоритмом проверки соответствие теоремы и доказательства. А вот какой размер доказательства будет допустимым в базовой проверке – это мы зададим специальными аргументами размера. Тогда «Сфинкс» для интересующих нас аргументов примет такой вид: 

Sph(d, t, S, s, y)

Где S – число, задающее максимальную длину доказательства. Число S записано в десятичном (например) виде, а s – соответствующая (иначе алгоритм проверки выдаст 0) данному числу S строка из символов «1» длиной S символов, например. Но длина строки s может быть равна, скажем, и S^{1/10}. То есть – корень десятой степени от S. Можно поставить корень любой фиксированной степени – всё равно размер |s| будет неполиномиально больше размера числа S, записанного в стандартном позиционном (десятичном, к примру) виде.

Для чего нужна строка s? Для того, чтобы размер проверяемого доказательства имел какое-то полиномиальное соответствие с размером аргументов. В случае аналогичной задачи из класса NP+ все рассуждения оказываются значительно проще, а аргумент s исчезает из рассмотрения. Но будем разбираться сразу с задачей из класса NP, а задача из класса NP+ будет разобрана при этом автоматически – методом сокращения рассуждений, связанных с аргументом s.

Аргументы S, s будем называть «аргументы размера». Аргумент S будем называть «число из аргументов размера», а аргумент s – «строка из аргументов размера».

2.2. Условимся об обозначении – правильный аргумент s получается тогда, когда s = s1(S). То есть, алгоритм s1(S) генерирует строку из символов «1» нужного для корректного s размера. Если строка s отличается от результата s1(S), то базовый алгоритм проверки задачи «Сфинкс» возвращает 0 (Ноль). Для базовой проверки значение аргумента долга будет – «объективно», то есть, равным символу «-».

3. Начнем реализацию плана, намеченного в пункте 1.1.

Рассмотри алгоритм «Эдип» с теоремой о результате работы алгоритма «АнтиЭдип», аргументом долга «объективно» (значение аргумента «-») и числом из аргументов размера S:

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s)

Для написанного алгоритма «Эдип» с приведёнными аргументами нам нужен такой алгоритм «АнтиЭдип», на основе которого будет сформирована теорема AntiOed_S() = 0. Разумеется, для разных S будут разные «АнтиЭдипы». Алгоритм AntiOed_S() работает следующим образом:

3.1. Формирует текст теоремы

«AntiOed_S() = 0»

3.2. Запускает «Эдипа» со следующими аргументами:

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))

Притом в программном коде алгоритма «АнтиЭдип» строка из аргументов размера «Эдипа» генерируется из сжатого представления: Соответствующей переменной присваивается результат работы s1(S), а уже значение переменной будет использоваться в качестве строки из аргументов размера при запуске «Эдипа». Таким образом, размеры программного кода алгоритма «АнтиЭдип» и теоремы AntiOed_S() = 0 будут неполиномиально малы относительно строки s из аргументов размера «Эдипа» с нужными нам аргументами.

3.3. Ждет результата работы «Эдипа» и действует в зависимости от того, что выдаст «Эдип»:

3.4. Если Эдип возвращает 0 – «не могу найти доказательство», то «АнтиЭдип» возвращает в качестве результата 0 и останавливается, доказав делом теорему AntiOed_S() = 0

3.5. Если «Эдип» возвращает какую-то строку в качестве доказательства, то «АнтиЭдип» пытается выделить результат доказательства – утверждение AntiOed_S() = 0 в качестве последнего шага доказательства. И действует в зависимости от успеха такого выделения:

3.6. Если выделение не удалось, то теорема не доказана и исполняется пункт 3.4.

3.7. Если выделение удалось, то AntiOed_S() возвращает 1 и останавливается. Доказав делом, что теорему AntiOed_S() = 0 нельзя доказать.

Замечание. В построении нашей задачи и обосновании её свойств мы сейчас неявно использовали непротиворечивость той теории, которая лежит в её основе (теория Пеано или подобная ей). Именно об этом и говорилось в разделе 3 «Сложность вопроса о NPP»:

В противоречивой теории было бы доказано всё – в том числе доказательство чего угодно мог бы найти и «Эдип» – независимо от того, как бы работал «АнтиЭдип». И, кстати, принцип независимости алгоритма проверки был бы нарушен.


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

  • 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