dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Постановка задачи про NP≠P («нечестная») и сведения из учебников.

Почему постановка задачи «нечестная» и в кавычках - будет сказано в начале следующей записи.

В развитие предварительного эвристического доказательства.

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

Теорема дедукции

В своем доказательстве я буду использовать теорему дедукции. Скажу как и для чего её применяют, а затем докажу. В логике часто используют такую схему вывода:

Шаг 1. Гипотеза: C

....  всякие логические выводы на основе правила вывода MP (когда из истинных (A => B) и A делают вывод об истинности B) и используя C как истину...

Шаг N. Результат вывода из гипотезы C: A

Шаг N+1. Результат вывода без всякой гипотезы C: (C => A)

Вот такая методика. Она основана на том, что на каждом шаге вывода есть некая текущая промежуточная формула X. И на каждом шаге эту промежуточную формулу можно заменить на истинную формулу (C => X). И уже без всякой гипотезы. Тогда Шаг N действительно превратиться в Шаг N+1, а Шаг 1 превратиться в тавтологию (C => C).

Как сделать такой переход, если используем только правило вывода MP? Достаточно разобрать один пример, чтоб понять. Пусть есть такой вывод пункта 3 из пунктов 1 и 2 по правилу MP:

1.       Выведено раньше: A => B

2.       Выведено раньше: A

3.       Из пп. 1 и 2 получим: B

А нужно заменить это на следующее:

1.       Выведено раньше: C => (A => B)

2.       Выведено раньше: C => A

3.       Из пп. 1 и 2 получим: C => B

Но такую последовательность надо дополнить промежуточными шагами, чтобы использовать только правило вывода MP и аксиомы теории. Для этого подойдет тавтология:

C => (A => B) => [ (C => A) => (C => B) ]

Тогда по правилу MP в этой тавтологии убирается начало, совпадающее с п.1, затем начало от остатка, совпадающее с п.2 и остается то, что в п.3. Иногда данную тавтологию делают одной из аксиом логики (для удобства доказательства теоремы дедукции, видимо), впрочем, она не наглядна в качестве исходного истинного утверждения.

Поэтому там, где я буду использовать теорему дедукции – можно написать и «механический» вывод из истинных утверждений при помощи MP без всяких гипотез. Кто хочет – может это легко проделать, но тут для краткости я будут использоваться теорему дедукции.

Нужная тавтология


Еще я буду использовать тавтологию (X1 => Y) => [ (X2 => Y) => ( (X1 Ú X2) => Y ) ]. Разумеется, ее можно вывести из аксиом логики (из аксиом логики по теореме о полноте можно вывести любую тавтологию), но просто покажу, что это тавтология:

1. Раскроем данное утверждение, заменяя импликацию (A => B) на эквивалентную ей дизъюнкцию (~A Ú B):

           ~(~X1 Ú Y) Ú [ ~(~X2 Ú Y) Ú ( ~(X1 Ú X2) Ú Y ) ]

2.Заменим ~(A Ú B) на эквивалентное утверждение (~A Ù ~B), а (~~A) на (A) и уберем лишние скобки для ассоциативной операции Ú:

(X1 Ù ~Y) Ú (X2 Ù ~Y) Ú (~X1 Ù ~X2) Ú Y

3. Воспользуемся дистрибутивностью операции Ù:

((X1 Ú X2) Ù ~Y) Ú (~X1 Ù ~X2) Ú Y

В результате мы получили утверждение, эквивалентное исходному утверждению. Оно истинное, если истинно Y в силу последнего члена дизъюнкции Y. А если Y ложное, то утверждение будет истинным при истинности любого из X1, X2 – в силу первого члена дизъюнкции ((X1 Ú X2) Ù~Y). Но если и они ложные – то выражение все равно истинное в силу среднего члена дизъюнкции (~X1 Ù ~X2). Поэтому – это тавтология.

Лемма о диагонализации


В доказательстве теоремы NP P будет использована возможность подставлять в алгоритм A(x) текст самого алгоритма.

Чтоб отличить в формулах алгоритмы от их текстов, буду обозначать текст алгоритма кавычками вокруг обозначения алгоритма. Вот так, например: «AntiMt()»

Очевидно, что всегда можно сделать алгоритм AA, который сначала выписывает текст алгоритма A(x), а затем запускает алгоритм A(x) с этим текстом в качестве аргумента. Так вот, у этого алгоритма AA тоже есть текст его «программы», и этот текст может быть получен из текста алгоритма A по некоторому алгоритму diag(«A(x)»). Это довольно очевидно и такая возможность берется за исходную посылку. То есть - нам нужны достаточно выразительные теории, которые способны представлять алгоритмы и тогда алгоритм diag() - будет среди них.

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

Поэтому за основу возьмем Лемму о диагонализации из книги «Вычислимость и логика» Дж. Булос, Р. Джеффри. Только там она для предиката доказана, а мы докажем ее для алгоритма. В остальном я практически переписываю доказательство. И еще один момент - там доказательство на основе «представлений», а я оперирую с алгоритмами - логика та же, просто через представления возникает дополнительный «этаж» манипуляций, но мы просто можем считать, что наша теория более выразительная, чем теория Пеано и можно оперировать прямо со свойствами алгоритмов.

Лемма о диагонализации. Для произвольного алгоритма B найдется алгоритм G, такой что G = B(«G»).

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

Назовем алгоритмом G() тот алгоритм, который выполняет расчет как B(diag(«B(diag(x))»)). Собственно, G() отличается от B(diag(«B(diag(x))»)) только тем, что алгоритм G сначала выписывает аргумент  «B(diag(x))», а затем запускает композицию функций B(diag(...)) с этим аргументом. И - текст этого алгоритма G получается вот так: diag(«B(diag(x))»). Ведь алгоритм diag() построен именно так, чтоб возвращать текст подобных алгоритмов.

1. По свойствам diag(): «G()» = diagB(diag(x))»)

2. По построению G(): G() = B(diagB(diag(x))»))

3. Из п. 1 подстановкой частей равенства в B(): B («G()») = B(diag(«B(diag(x))»))

4. Из пп. 2 и 3: B(«G()») = G()

Лемма доказана.

Вот так мы переписали доказательство для предикатов в доказательство для алгоритмов. И вся разница между предикатом и алгоритмом в том - что вместо значка эквивалентности в последнем предложении стоит знак равенства. Но по сути тут огромное отличие. Ведь алгоритм выдает при одних и тех же аргументах один и тот же результат - и если он не останавливается, то он нигде не останавливается. И ни от какой теории это не зависит. И поэтому можно построить «Универсальный алгоритм», который полностью моделирует поведение алгоритма-аргумента (точнее, алгоритма, чей текст передан в качестве аргумента).

А вот у предиката нет возможности «не останавливаться» - у него нет своей «самостоятельной жизни» вне теории. Поэтому с предикатами нет возможности построить универсальный предикат, который получал бы текст другого предиката и был точно таким же истинным или ложным как он:

Ведь универсальный предикат при помощи отрицания становится универсальным анти-предикатом, который всегда возвращал бы противоположное, чем предикат-аргумент (точнее, предикат, чей текст получен в качестве аргумента). А это невозможно, потому что по лемме о диагонализации найдется эквивалентный предикат для данного анти-предиката. Значит, универсальный анти-предикат невозможен, значит, невозможен и универсальный предикат.

В ходе доказательства теоремы NP P мы увидим, как это различие между предикатами и алгоритмами выльется в существенное отличие получившейся неполноты от конструкции теорем Гёделя.

Постановка задачи

Рассмотрим следующую задачу из класса NP, сформулированную в 2-ух пунктах:

1. Имеется некоторая непротиворечивая (важно!) система аксиом Aks. В качестве слов будем рассматривать A() – записанные на языке теории алгоритмы. В качестве слова-свидетеля будем рассматривать текст доказательства для A() = i. Где i – некоторое число (можно считать, что число записано в десятичном представлении, но это не принципиально). Если имеется слово x и слово-свидетель y, то, как известно из логики, можно при помощи алгоритма автоматической проверки доказательств R(Aks, x, y) за полиномиальное время (число шагов) Py(|y|+|Aks|) от размеров y и Aks проверить, доказывает ли y какое-то равенство A() = i для x на базе аксиом Aks. На размер y накладывается стандартное для NP ограничение некоторым полиномом Px(|x|). Разумеется, если в качестве x и/или y выступает какой-то бессмысленный текст, то R(Aks, x, y) возвращает «ложь».

Размеры всех упомянутых полиномов считаем достаточно большими для наших целей - по контексту будет видно, что это легко достижимо.

2. Если система аксиом Aks противоречива или это какой-то бессмысленный текст, то в качестве R(Aks, x, y) выбран предикат, который всегда выдает «ложь» и  явно быстрее, чем Py(|y|+|Aks|).

Берем нашу задачу из пунктов 1 и 2. Берем метод поиска слов-свидетелей y, подходящих для заданного слова  x (то есть, |y| < Px(|x|) и R(Aks, x, y) дает истину). Назовем наш метод поиска слов-свидетелей для  слова  x - алгоритмом Mt(Aks, x).

Есть мнение, что всегда есть метод поиска, который всегда находит нужное слово-свидетель, если оно вообще есть. Это - прямой перебор всех y, таких что |y| < Px(|x|). Это мнение ошибочно, как мы увидим, в силу пункта 2 нашей задачи. А если бы было верно NP = P, то у нас был бы алгоритм поиска, который находил бы слово-свидетель (если оно есть) за полиномиальное время. Но мы докажем, что любой метод будет неполон - если он корректен, поэтому насчет полиномиальности скорости поиска мы даже не будем думать, главное, чтоб алгоритм поиска завершал свою работу в пределах заранее известного (от размера заданного слова и аксиом) времени.

Для простоты считаем, что Mt(Aks, x) выдает не текст доказательства (слово-свидетель), а результат этого доказательства (число i в некотором представлении) как прогноз результата работы алгоритма A(). Напомню, что текст некоторого алгоритма A() подставлен на место переменной x, когда решается вопрос про результат работы этого алгоритма.

Наше упрощение (результат вместо доказательства) вполне уместно, потому что мы будем опровергать полноту, а полный метод обнаружения доказательств давал бы возможность и для полного метода обнаружения результатов (для которых есть подходящее доказательство). Поэтому если нет полного метода для результата, то нет полного метода и для доказательств.

Если же нужного доказательства среди подходящих по размеру доказательств найти не удалось, то Mt(Aks, x) возвращает knockout. Ясно, что результаты Mt не прямо равны результатам A() - просто потому, что результаты могут быть какие угодно, а нам надо еще занять место для knockout, который ведь тоже может выдаваться какими-то алгоритмами. Есть разные способы ставить значения в соответствие друг другу, например - канторова пара из признака 1 и результата работы A(), либо просто 0 и 0 - для knockout.

Просто введем следующее обозначение для соответствия результатов самих алгоритмов и результатов прогнозов для них от Mt:

Если A() = i, и Mt(Aks, «A()») выдает правильный прогноз, то Mt(Aks, «A()») = FormatMt(i).

Разумеется, FormatMt(i) обратим - то есть, по нему можно узнать i. И FormatMt(i) никогда не возвращает knockout.

Теперь сформулируем частичное условие корректности для Mt(Aks, x) при x = «A()»:

Check100Mt(Aks, «A()») => 

( [ Mt(Aks, «A()») = FormatMt(A()) ] Ú [ Mt(Aks, «A()») = knockout ] )

Сначала рассмотрим заключение в данной импликации:

[ Mt(Aks, «A()») = FormatMt(A()) ] Ú [ Mt(Aks, «A()») = knockout ]

Очень важно, что FormatMt(A()) не зависит от аксиом, хотя Mt зависит. И мы можем написать это равенство благодаря п.2 нашей задачи. Потому что если заданные аксиомы выдают абсурдные выводы про работы алгоритмов, то это противоречие и эти выводы не имеют значения и в силе будет (Mt(Aks, «A()») = knockout). Противоречие возникнет из-за 2х разных выводов про результат работы A() - эталонного (который отражают теоремы Пеано без расширений, например) и ложного.

Но проблема в том, что алгоритм A() может ведь и не остановится. И не будет эталона для сравнения. И в таких случаях есть угроза, что теория содержит непротиворечивую, хоть и абсурдную аксиому, что где-то в бесконечности алгоритм все же что-то вернет. Чтобы избежать таких накладок, мы будем рассматривать только алгоритмы с остановкой. И для этого у нас в частичной корректности есть посылка импликации:

Check100Mt(Aks, «A()»)

Это такой алгоритм, который проверяет, что разбираемый алгоритм A() делает меньше шагов, чем 100-кратное количество шагов работы у алгоритма Mt(Aks, «A()»). Технически это можно сделать последовательным исполнением того и другого по одному шагу. И если Mt(Aks, «A()») отработал 100 раз, а A() еще не закончил работу, то мы не можем пользоваться нашей частичной корректностью. Но зато когда можем - то мы уверены, что можем использовать для проверки FormatMt(A()) - который независим от аксиом.

Утверждение частичной корректности можно переписать с использованием универсального алгоритма U(x), который исполняет любой алгоритм по его тексту и возвращает результат (если остановится) в формате FormatMt(i). Если текст абсурден - то возвращает knockout. Как известно, универсальный алгоритм U(x) существует и его легко построить - в отличие от универсального предиката. О чем уже было сказано в разделе «Лемма о диагонализации». Тогда мы могли бы вместо «A()» поставить x и квантор общности, но нам частичная корректность потребуется только для одного алгоритма, поэтому сойдёт и так.

И, разумеется, время (количество шагов ) работы Mt(Aks, x) конечно и ограничено некоторым всюду определённым алгоритмом T(|Aks| + |x|).

То, что сформулировано про корректность - сформулировано «со стороны». Мы как бы рассматриваем Mt(Aks, x) в какой-то непротиворечивой теории, притом аксиомы этой теории не обязательно равны аксиомам Aks. И принцип корректности, кстати, распространяется и на противоречивые теории - в соответствии с пунктом 2. А противоречивую теорию можно рассмотреть только с точки зрения непротиворечивой.

Существует ли хоть одна корректная Mt? Да - которая всегда возвращает knockout, например.

План доказательства такой:

Сначала мы изучаем свойства Mt(Aks, x) «со стороны» (всегда есть непротиворечивая теория, соответствующая арифметике в стандартной интерпретации , в которой можно изучить Mt(Aks, x) - с заданным в ней Aks), затем мы делаем выводы о поведении Mt(Aks, x) в целом - при любых Aks, на основании этого выписываем истинное в стандартной интерпретации арифметики свойство, берем его в качестве аксиомы, расширяем им непротиворечивую теорию. Теория остается при этом непротиворечивой, а затем в этой теории доказываем неполноту Mt(Aks, x). Перейдем к реализации этого плана.

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