dmitgu (dmitgu) wrote,
dmitgu
dmitgu

NP ≠ P. Техническое доказательство («нечестное»)

Предварительно скажу кое-что про «окрестности» доказательства. Очень похоже (вообще я уверен, но мало ли...), что в теории алгоритмов есть парадокс (попросту ошибка), когда математики ставят состав математического объекта (класс задач NP) в зависимость от своих знаний. Об этом я писал в предварительном эвристическом варианте. Суть в том, что они хотят, чтоб туда входили лишь задачи, чей алгоритм проверки они знают. Хотя есть задачи, чей алгоритм проверки удовлетворяет требованиям класса NP, но какой это алгоритм - решения в общем случае нет. И приводимое ниже мое доказательство для NPP существенно опирается на невозможность решить вопрос - какой там реально алгоритм в общем случае.

Но - если уж быть честным - есть и задачи из класса NP, чей алгоритм действительно известен, либо который можно найти в общем случае. И для этого частного случая требуется отдельное доказательство, что этот solvab_NP (назову так этот подкласс в NP от английского solvability - разрешимость) тоже не сводится к P. И, когда ставился вопрос про NP P, то хотели спросить - я так понимаю - про solvab_NP P. Даже, пожалуй, они хотели знать про те задачи из NP, чей алгоритм проверки разрешим (его можно узнать) за полиномиальное число шагов (где полином зависит от размера формулировки данной задачи, грубо говоря). Вопрос типа p_solvab_NP P.

В этом смысле я как бы не тянусь ручонками к премии в миллион баксов (которая как бы положена), потому что хоть они и спросили и я ответил (гм.. если..) именно на заданный (подходя формально) вопрос, но все же хотели они спросить иное. «Я мзду не беру, мне за державу обидно» ((с) Белое солнце пустыни). В том смысле, что дело не в деньгах, а в математике. И если парадокс верен - который я обнаружил - то это не менее важно, чем NP P.

И тогда парадокс надо все же признать и переделывать существенную часть теории алгоритмов, либо указать, какая у меня ошибка. Я же могу обратиться за разъяснением? Вот к водопроводчику же могу, когда возникла проблема, а кто выполняет работу по вопросам математики? Потому что это тоже вопрос, который касается населения (обучения в частности - речь идет про теоремы из типичных учебников по теории алгоритмов - и это принципиальные теоремы для данной специальности) и его тоже должен кто-то решать.

Да, а если я докажу p_solvab_NP P (что возможно - в тему я влез хорошо у чувствую её), то я за деньгами обращусь есно - отказываться было бы тогда нарушением прав и вредно для общества и самого себя.

Копирую сюда свою запись ( http://dxdy.ru/post956292.html#p956292 ) с форума dxdy.ru от 04 января 2015 г.

Завершаю техническое доказательство, начатое здесь: http://dmitgu.livejournal.com/111548.html

(некоторые интересные замечания есть в предварительном эвристическом варианте и не вошли в данный)

Доказательство «со стороны»

Как было намечено планом доказательства в предыдущем разделе, рассмотрим свойства алгоритма Mt(Aks, x) силами некой непротиворечивой теории-обоснования. Ее аксиомы не обязательно совпадают с Aks, но соответствуют стандартной модели арифметики. Тогда выводы, сделанные про работу алгоритма Mt(Aks, x) будут верны независимо от теории.

Для начала построим алгоритм AntiMt(), который будет «обманывать» Mt(Aks, x). Идея в том, что AntiMt() запускает внутри себя копию Mt(Aks, x), передав в качестве X свой собственный текст и выдает противоположное тому, что получит от своей копии Mt(Aks, x). Тогда Mt(Aks, x) не сможет прогнозировать результат AntiMt().

AntiMt - это алгоритм, текст которого можно получить так: diag(«Anti(Mt(Aks, x))»), где Anti(x) преобразует результат в 0, если аргумент отличается от FormatMt(0), и в  1, если аргумент совпадает с FormatMt(0). Сделано так, чтоб выдать противоположное, чем об этом мог бы «сказать» Mt.

По лемме о диагонализации имеем: Anti(Mt(Aks, «AntiMt()»)) = AntiMt().

Очевидно, что построенный AntiMt() удовлетворяет посылке Check100Mt(Aks, «AntiMt()») в частичной корректности и частичную корректность можно переписать так (исключив посылку по правилу вывода MP):

[ Mt(Aks, «A()») = FormatMt(A()) ] Ú [ Mt(Aks, «A()») = knockout ] или, иначе:

~(  Mt(Aks, «A()»)=FormatMt(A())  ) => (  Mt(Aks, «A()») =knockout  ) или, то же самое:

(  Mt(Aks, «A()») FormatMt(A())  ) => (  Mt(Aks, «A()») = knockout  )

Теперь можно переходить к выводу утверждений, которые будут использованы в доказательстве неполноты алгоритма Mt(z, x) на соответствующем ему (по аксиомам z) AntiMt()

Теорема. Mt(Aks, «AntiMt()») = knockout, в то время как AntiMt() = Anti(knockout)

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

1. По построению AntiMt(): Anti(Mt(Aks, «AntiMt()»)) = AntiMt().

Это означает, что то, что возвращает Mt про результат работы AntiMt() не совпадает с реальным результатом AntiMt() и, возможно, противоположно (из-за функции Anti()) реальному результату. Но это мы аккуратно выведем далее.

2. FormatMt(Anti(x)) ≠ x

Ниже будет подробно рассмотрен вывод этого пункта – он длиннее всего остального, хотя само неравенство очевидно – ведь алгоритм Anti() как раз так построен, чтобы из результата работы алгоритма Mt делать иное значение в смысле формата Mt – чтобы «оспорить» результат работы Mt, который получил на вход текст алгоритма AntiMt. Поэтому в п. 2{C}{C}{C}{C}я оставил очевидное неравенство без вывода, чтоб не загромождать основной вывод и не снижать его ясность. А чтобы сохранить техническую полноту доказательства, вывод для пункта 2{C}{C}{C}{C}приведен сразу вслед за текущим (основным) выводом.

3. Из п. 1, применяя FormatMt() к обеим частям равенства:

FormatMt(Anti(Mt(Aks, «AntiMt()»))) = FormatMt(AntiMt())

4. Из п.2 - заменив x на Mt(Aks, «AntiMt()») получим:

FormatMt(Anti(Mt(Aks, «AntiMt()»))) ≠ Mt(Aks, «AntiMt()»)

5. Из пп. 3, 4 и аксиомы для равенства получим:

Mt(Aks, «AntiMt()») ≠ FormatMt(AntiMt())

6. Свойство корректности: ( Mt(Aks, «A()») ≠ FormatMt(A()) ) => ( Mt(Aks, «A()») = knockout ), где «A()» - текст произвольного алгоритма, удовлетворяющего Check100Mt(Aks, «A()»).


7. Из п. 6 подстановкой «AntiMt()» (она удовлетворяет Check100Mt(Aks, «AntiMt()»), как было отмечено при ее построении) вместо «A()» получим:

( Mt(Aks, «AntiMt()») ≠ FormatMt(AntiMt()) ) => ( Mt(Aks, «AntiMt()») = knockout )


8. Из пп. 5 и 7 по правилу вывода MPMt(Aks, «AntiMt()») = knockout

9. Из п. 8, применяя к обеим сторонам равенства Anti() получим:

Anti(Mt(Aks, «AntiMt()»)) = Anti(knockout)

10. Из пп. 1 и  9 получим: AntiMt() =  Anti(knockout)

С учетом того, что алгоритм Anti() является крайне примитивным и быстрым, результат Anti(knockout) вычисляется моментально. А это значит, что в рассматриваемой теории-обосновании доказано, что в результате своей работы алгоритм AntiMt() даст результат Anti(knockout), о чем заведомо не в состоянии сообщить алгоритм Mt(Aks, «AntiMt()»), так как он в данном случае в соответствии с п. 8 выдает результат knockout (который не может соответствовать никакому значению).

Теперь – обещанный вывод неравенства ( FormatMt(Anti(X)) ≠ x ) из п. 2. Вывод – из свойств Anti() и свойств результатов, которые выдает алгоритм Mt. Эти свойства сформулированы в первых трех пунктах вывода:

2a. Свойство алгоритма Anti(): ( x ≠ FormatMt(0) ) => ( Anti(x) = 0 )

2b. Свойство алгоритма Anti(): ( x = FormatMt(0) ) => ( Anti(x) = 1 )

2c. Свойство обратимости для FormatMt(): FormatMt(0) ≠ FormatMt(1)

2d. Гипотеза: x FormatMt(0)

2e. Из пп. 2a и 2d по правилу вывода MP: Anti(x) = 0

2f. Из п. 2e, применяя к обеим сторонам FormatMt:                FormatMt(Anti(x)) = FormatMt(0)

2g. Из пп. 2d, 2f и аксиом равенства: FormatMt(Anti(x)) ≠ x

2h. Из пп. 2d, 2g и теоремы дедукции: ( x ≠ FormatMt(0) ) => ( FormatMt(Anti(x)) ≠ x ). После этого гипотеза 2d исключена из рассмотрения. В процессе использования гипотезы никакие правила вывода кроме MP не применялись (это упоминание о нюансе в формулировке теоремы дедукции, что упрощает её применение).

2i. Гипотеза: x = FormatMt(0)

2j. Из пп. 2b и 2i по правилу вывода MP:          Anti(x) = 1

2k. Из п. 2j, применяя к обеим сторонам FormatMt: FormatMt(Anti(x)) = FormatMt(1)

2l. Из пп. 2c, 2i и аксиом равенства: x ≠ FormatMt(1)

2m. Из пп. 2k и 2l: FormatMt(Anti(x)) ≠ x

2n. Из пп. 2i, 2m и теоремы дедукции: ( x = FormatMt(0) ) => ( FormatMt(Anti(x)) ≠ x ). После этого гипотеза 2i исключена из рассмотрения. В процессе использования гипотезы никакие правила вывода кроме MP не применялись (это упоминание о нюансе в формулировке теоремы дедукции, что упрощает её применение).

2o. Тавтология: (X1 => Y) => [ (X2 => Y) => ( (X1 Ú X2) => Y ) ]

2p. Если положить, что X1 это [ x ≠ FormatMt(0)], X2 это [x = FormatMt(0)], а Y это [FormatMt(Anti(x)) ≠ x], то 2h будет иметь вид (X1 => Y) и из пп. 2h, 2о по правилу MP получим:

(X2 => Y) => ( (X1 Ú X2) => Y )

2r. С теми же обозначениями, что в п. 2p пункт 2n будет иметь вид (X2 => Y) и из пп. 2n, 2p по правилу MP получим: ( X1 Ú X2) => Y

2s. Теперь раскрываем оговоренные в п. 2p обозначения применительно к п. 2r и получаем:

([x ≠ FormatMt(0)] Ú [x = FormatMt(0)]) => [FormatMt(Anti(x)) ≠ x]

2t. В тавтологию (X Ú ~X) подставим вместо X выражения [x = FormatMt(0)] и получим:

([x FormatMt(0)] Ú [x = FormatMt(0)])

2u. Из пп. 2s, 2t и правила вывода MP получим: FormatMt(Anti(x)) ≠ x

Вот мы и получили пункт 2:

2. FormatMt(Anti(x)) ≠ x

Теорема доказана.

Завершение доказательства

Теорема.  Mt(z, x) является неполной. То есть, найдется непротиворечивая теория с аксиомами Aks, в которой доказан результат работы некоторого алгоритма A() и размер этого доказательства меньше Px(|«A()»|), но алгоритм Mt(Aks, «A()») возвращает knockout.

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

Мы выяснили, что Mt(z, «AntiMt()») = knockout истинно всегда (точнее сказать «для достаточно выразительных теорий», для строгости можно рассматривать только расширения теории Пеано). Просто так работает алгоритм. Значит, это утверждение можно добавлять в непротиворечивые теории арифметики и будут получаться непротиворечивые теории арифметики. Берем достаточно выразительную теорию арифметики, добавляем в неё эту аксиому (замечу, что никаких утверждений корректности уже не требуется) и получаем некоторую новую непротиворечивую теорию с аксиомами Aks.

А теперь подставим в эту аксиому Mt(z, «AntiMt()») = knockout вместо z эти самые Aks.

При подстановке вместо z текстов аксиом Aks получаем Mt(Aks, «AntiMt()») = knockout. Берем пункты 8, 9 и 10 из предыдущего раздела (тут доказательство уже не «со стороны») и получаем доказательство для результата AntiMt(). Правда, в п. 10 есть ссылка на п.1, но это ссылка на свойства диагонализации - которая является общим свойством для всех алгоритмов и доказывается для любого из них в достаточно выразительной теории. И небольшой размер этого доказательства тоже известен (кстати, его тоже можно аксиоматизировать для краткости - тут всё истинно).

Итак, в непротиворечивой теории с аксиомами Aks есть короткое доказательство для результата AntiMt(). Для того результата, который при всей его краткости не может сообщить Mt. Это значит, что задачу из класса NP, которая имеет подходящие слово и слово-свидетель, не удается решить силами алгоритма Mt - если этот алгоритм корректен. А это значит, что NP P.

Теорема доказана.

Замечание.  Фокус доказательства в том, что фактически мы можем проверить (со стороны!) что вернет AntiMt() и что вернет Mt(Aks, «AntiMt()»). И противоречий не должно возникнуть. И Mt это «понимает» и «понимает», что если он даст какой-то значимый результат для AntiMt(), то теория получится противоречивой и ему всё равно «придется» выдавать knockout. В результате он «не спорит» с аксиомой Mt(z, «AntiMt()») = knockout, потому что всё равно «проиграет».

И ещё один интересный момент. При желании, видимо, можно ослабить требования пунктов 1 и 2 в постановке задачи. Ведь в утверждении корректности нам не требуется противоречие через неограниченное количество шагов. Поэтому пункт 1 можно, наверно, ослабить до требования «условной непротиворечивости» - на глубину работы проверяемых Mt(Aks, «AntiMt()») и AntiMt(), а пункт 2 - до уровня грубой противоречивости - которую можно выявить на той же глубине поверки. Однако это внесло бы дополнительную громоздкость в доказательства, а нас же тут интересует сам принцип, а не широта вариантов.
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