January 7th, 2015

ёжик

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

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

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

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

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

Collapse )

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

Collapse )

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


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

Collapse )

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

Рассмотрим следующую задачу из класса 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).

Collapse )

ёжик

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

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

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

Collapse )