dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 7, пп. 6.1-6.3. NP ≠ P

к Оглавлению

6. Теперь начнем реализацию заключительного этапа нашего плана – пункта 1.3. Хотя уже сейчас из пункта 5.6 довольно очевидно, что корректный «Эдип» должен будет дать очень быстрый ответ по меркам «общего» ограничивающего алгоритма. А выдав такой ответ быстро – он сделает и ответ «АнтиЭдипа» очевидным, в силу чего доказательство о результате работы «АнтиЭдипа» окажется достаточно небольшим для того, чтобы не превысить величину S (или размер |s| - что то же самое). И тогда будет и время на ответ «Эдипа» - «не могу найти доказательство», и само доказательство допустимого размера, которое «Эдип» не смог найти. То есть – будет доказана неполнота корректного «Эдипа». А так как «Эдип» - произволен, то будет доказано и NPP – неполнота разбираемой задачи из класса NP с точки зрения её сводимости к задаче из класса P силами произвольного алгоритма.

6.1. Допустим, что алгоритм «Эдип» в интересующем нас случае остановился и вернул результат 0. Любой другой результат был бы ошибочным в случае остановки, как мы видели. А не-остановка тоже была бы ошибкой, так как информация о невозможности решить «Эдипу» интересующую нас задачу имеется – достаточно запросить «Сфинкса» об этом.

Ещё один момент – в интересующем нас случае s = s1(S), так как в противном случае правильный результат – 0 (Ноль) и мы не ищем в этом случае неполноты «Эдипа».

Вопрос: Какой размер доказательства будет после такой остановки у интересующей нас теоремы:

AntiOed_S() = 0

6.2. Понятно, что алгоритм AntiOed_S() тоже остановится в случае остановки «Эдипа» - так построен алгоритм AntiOed_S(), что он завершает свою работу после остановки «Эдипа» с соответствующими параметрами.

Доказательство того, что если остановится «Эдип» в интересующем нас случае, то остановится и «АнтиЭдип» будет полиномиального размера относительно размера «Эдипа», даже независимо от размера |S| - пока вместо конкретного значения S рассматривается некая переменная:

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

Но при подстановке S для конкретного значения зависимость появится, при этом исполнять s1(S) не придётся. Например, для формулы:

OedSph(…, …, …, …, …)», «-», «AntiOed_{100000}() = 0», 100000, s1(100000)) = 0  AntiOed_{100000}() = 0

Размер доказательства данной формулы будет полиномиального размера относительно размера «Сфинкса» и 6 (шести - количества цифр в 100000).

6.3. Итак – какого размера будет доказательство следующего выражения, в которое подставлено конкретное S, но не исполнено ещё s1(S):

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

Размер доказательства данного выражения надо оценить относительно его размера (включая подставленное конкретное значение S) и количества шагов работы алгоритма «Эдип» из данного выражения, если «Эдип» завершает свою работу через n шагов и в это число n не входит время работы s1(S).

Разумеется, мы можем «перевести» каждый шаг работы программы в несколько шагов доказательства, полиномиально зависящих от размера программы и размера занятой переменными и аргументами памяти. Но работу конкретно алгоритма s1(S) таким образом «переводить» в доказательство нет никакой нужды. Так как результат работы s1(S) заранее известен.

6.3.1. Для каждой ячейки памяти аргумента s, которая получает своё значение после исполнения s1(S), нам известно как её значение (символ «1»), так и количество соответствующих ячеек (их количество - S). И в тексте доказательства для разбираемого выражения, каждый шаг работы алгоритма «Эдип», в которой он делает операцию с одной из ячеек памяти аргумента s, будет «переведён» в полиномиальное количество шагов доказательства. Притом «полиномиальное количество» - это относительно вот чего:

размера |OedSph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n.

Надо пояснить, что после того, как s1(S) исполнен, состояние программы пришло в «исходное положение», аналогичное запуску алгоритма с готовыми аргументами (так мы строим подстановку аргументов):

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

И переход из этого состояния в последующие будет полностью задаваться номером очередного шага in, от которого и будет полиномиально зависеть размер шагов доказательства, соответствующих этому шагу работы. Размер самого аргумента |s| при этом может не иметь никакого значения для размера шагов доказательства о данном шаге работы – ведь программа всё равно не может обратиться к числу ячеек переменной s, превышающему само n и имеет дело с той частью аргумента s, ячейки которого доступны через «индекс» in.

Сделанное замечание остаётся в силе и в том случае, если учитывать ограниченность скорости света и отчасти использовать модель «машины Тьюринга» - тогда добраться до конкретной ячейки памяти надо за несколько шагов работы программы, но тогда тем более количество использованных в процессе работы ячеек окажется меньше n.

И каждый шаг доказательства в отношении работы с ячейкой памяти s по своему размеру (количеству символов) сам будет полиномиальным от данных величин. Значит, размер всех таких шагов доказательства (количество символов в них) будет полиномиальным относительно тех же размеров. Ведь таких шагов – меньше n. «Меньше» - потому что не все шаги работы программы будут операциями с аргументом s.

6.3.2. Таким образом, времени работы алгоритма s1(S) в нашем доказательстве не соответствует ничего, сопоставимого по своим размерам со временем его работы. Но какое-то небольшое количество предварительных шагов доказательства, соответствующее заполнению аргумента s алгоритмом s1(S), в доказательстве будет сделано для дальнейшего применения в пункте 6.3.1. Будем считать – тоже полиномиальное количество символов у этой «предварительной» части доказательства (хоть это и с запасом – n лишнее, видимо) от

размера |Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n

6.3.3. Остальные шаги работы алгоритма

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

обычным образом «переводятся» в шаги доказательства о работе данного алгоритма – вплоть до его остановки. Размер (количество символов) каждого такого шага доказательства полиномиально относительно:

размера |OedSph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n.

Количество шагов доказательства на каждый шаг работы алгоритма – полиномиальное относительно того же, а само количество шагов программы – кроме тех, что разбирались в пунктах 6.3.1 и 6.3.2 – не больше n (меньше n, если была хоть одна операция «Эдипа» с аргументом s). Таким образом, размер всего доказательства (количество символов) помимо того, что рассмотрено в  пунктах 6.3.1 и 6.3.2 – полиномиально относительно:

размера |Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n.

6.3.4. Просуммировав пункты 6.3.1, 6.3.2 и 6.3.3 выясняем, что размер доказательства выражения

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

в случае остановки алгоритма из данного выражения с результатом 0, будет иметь размер полиномиальный относительно:

размера |Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n

Где n – количества шагов работы алгоритма «Эдип» из разбираемого выражения и в это число n не входит время работы алгоритма s1(S).

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