NP≠P. Док-во от противного-контрпример алгоритмов из NP

[m(Ax)]

То есть вопрос об противоречии в определении снят. А то, что определение не соответствует ожиданиям, так надо либо поправить ожидания, либо вводить новое. Все в Ваших руках, вводите новое и с ним работайте, сможете показать, что оно полезное будет почет и уважение)).

Дана задача $L'$, про $L$ ничего не известно. Вот, что такое "значимая часть"?

[dmitgu]

m(Ax) в сообщении #968464 писал(а):

дана задача $L'$, про $L$ ничего не известно. Вот, что такое "значимая часть"?

Наверно опечатка и точнее - "дана задача $L$, про $L'$ ничего не известно".

Да нет – про $L’$ очень даже известно: не будем забывать, что мы обсуждаем не $L$ сам по себе, а лишь как один из инструментов при обсуждении класса $NP$. И класс $NP$ считается быстрым в смысле алгоритма проверки. И если мы можем свести $L$ к «быстрому» $L’$ - то для этого класс $NP$ и создавался. Но этот $L’$ таков, что он сам может быть заменен на задачу из класса $P$. Получается, что наличие задачи $L’$ принципиально важно – если бы класс $NP$ включал в себя действительно те задачи, для которых его и создавали – для практически быстрых задач. Но мы видим, что его построение для данной цели нельзя считать завершенным.

Что касается «значимой» части проверяемого слова – это из логичного требования, которое уместно применить к задачам из класса $NP$:
Надо чтоб проверяемое слово нельзя было свести (полиномиально?) к паре $(A + B)$ - где $B$ - любое размера до $L$, и $L$ неполиномиально велико относительно $|A|$, но в смысле проверки от этого $B$ ничего не зависит.

Вот $B$ - это не-значимая часть проверяемого слова.

m(Ax) в сообщении #968464 писал(а):

То есть вопрос об противоречии в определении снят.

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

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

[m(Ax)]

Нет, не опечатка. Именно $L'$. Представим такую ситуацию: я придумал некоторую задачу $L$, по ней построил $L'$ и этой задачей озадачил Вас. А про $L$ не сознаюсь))). Как будете определять "значимую часть" $L'$? А если я задачу по другому буду раздувать и не скажу как?

[dmitgu]

m(Ax) в сообщении #968610 писал(а):

Представим такую ситуацию: я придумал некоторую задачу $L$, по ней построил $L'$ и этой задачей озадачил Вас. Как будете определять "значимую часть" $L'$?

Вы думаете, это моя проблема? ))) Я никак не буду определять значимую часть. Раз Вам она не важна - я просто решаю $L'$ как задачу $P$ и - если это построено на базе ДНФ - говорю, что теперь Вы можете решить любую задачу из $NP$, потому что они все сводятся к "подходящей" для Вас задаче $L'$. Да, надо будет накрутить экспоненциальную - относительно "нормальных" задач - добавку к проверяемому слову, но ведь она полиномиальная - эта добавка - относительно приемлемой для Вас задачи $L'$. Я закрываю акты выполненных работ, получаю Ваши денежки, а проблемы с экспонентой - они не мои ;)

[bilan]

Извините, может я Вас не так понял, но за какое время Вы найдете полинимиальный алгоритм, если он состоит например из $200000$ строк кода?

[dmitgu]

bilan в сообщении #972678 писал(а):

Извините, может я Вас не так понял, но за какое время Вы найдете полинимиальный алгоритм, если он состоит например из $200000$ строк кода?

Если Вы про последнюю шуточную пикировку, то я могу не решать чужую задачу а решить свою ) Ну, есть логическое уравнение (ДНФ) - я его увеличиваю "мусором" в экспоненту раз больше и после этого простой перебор решений для исходного уравнения - будет вполне себе полиномиален для новой задачи. А все остальные задачи "сводятся" к данной )))

[dmitgu]

Надо подвести промежуточные итоги и запланировать следующие действия.

Было сделано:

Предварительное эвристическое доказательство ( post954742.html#p954742 )

Сведения из учебников. Теорема о диагонализации в частности ( post956171.html#p956171 )

Моё первое формальное доказательство $NP \ne P$ тут с опорой на неразрешимость алгоритма проверки (для класса $NP$) + Определение $AntiMt$, вывод свойств ( post956292.html#p956292 )

Второе доказательство с расширенной проверкой корректности, но без опоры на неразрешимость проверк + Определение $DiagKnockout()$, вывод свойств ( post960183.html#p960183 )

Итоговое доказательство: Алгоритм $Mt$ не может всегда прогнозировать $AntiMt$, хотя должен, когда есть аксиома $DiagKnockout()$ ( post963495.html#p963495 )

Побочный разбор

По ходу построения доказательства возник «побочный» разбор нестыковок (на мой взгляд) в теории алгоритмов:
Класс - чрезмерное обобщение для $NP$, имхо. Скорее тип, вид - к которому ещё надо привести. Ну, например, не говорят о «классе» интегралов от дробно-рациональных функций - мы можем не знать, что данная функция равна дробно-рациональной, её надо ещё привести к нужному виду, а «класс» - это сразу готовый объект, независимо от вида. Но математик все же не бог, чтоб заранее знать всё.

Так же не могу согласиться - если подходить к этому строго - с обозначение $NP \ne P$ (или $NP = P$), потому что вопрос не о равенстве какой-то задачи из $P$ некой задаче из $NP$, а о возможности за конечное время найти соответствующее решение из $P$ для задачи из $NP$. Тут задача отчасти инженерная и такой практический параметр как время решения имеет принципиальное значение. В принципе, мое первое формальное доказательство тут обрывается именно после выявления невозможности свести при помощи конечного алгоритма некую задачу из класса $NP$ к задаче из класса $P$. Можно, кстати, доказать неравенство классов и вне связи с алгоритмом сведения (выбранный метод работы с алгоритмом-опровержением $AntiMt$ это позволяет), но это был бы ложный путь из-за необходимости - на мой взгляд - избавиться от использования тут понятия класса.

Есть и другие проблемы с определением задача из $NP$ (обсуждалось тут в комментариях) – в частности, возможность вырожденных (не значимых) частей у проверяемых слов, которые могут быть экспоненциально велики в сравнении со значимыми частями при нынешнем определении задач из $NP$.

Планы

Не взирая на обозначенные разногласия в понимании $NP$, в итоговом доказательстве выбрана такая задача, которая оказывается в $NP$ при любом его понимании – если бесспорно принадлежащие $NP$ задачи вообще могут решаться, как задачи из $P$. И в этом смысле доказательство $NP \ne P$ проходит при любом уточнении - «класс» это или «тип» $NP$.
Поэтому вопрос о противоречиях в понимании $NP$ можно будет обсудить отдельно, а доказательство $NP \ne P$ проведено независимо от разбора подобных противоречий, благо разбираемая задача допускает такой подход.

Если никто из читателей никаких ошибок в доказательстве не видит (а сам я их не вижу), то я должен делать следующий шаг и готовить статью для отправки в математический журнал, насколько я понимаю? Мне надо освоить подготовку документов в $LaTeX$ для публикации - что вроде потихоньку продвигается (удалось сверстать образцы из журнала «Математические заметки»). Подскажите пожалуйста - мне нужно самому везти туда распечатку или безнадега, раз это опубликовано на форуме? Еще мне надо здесь на форуме написать доказательство «одним куском», соединив в целое предыдущие «этапы» (или целостное доказательство я должен сделать только для журнала?) и написать аннотацию для журнала. Вот что у меня получилось в качестве аннотации пока что, подскажите пожалуйста, какие в ней недостатки:

Аннотация

Идея доказательства теоремы $NP \ne P$ типична для логики со времен теорем о неполноте и неразрешимости. А именно:
1. В качестве задачи $NP$ строится задача на базе проверки доказательства для результата работы заданного алгоритма в заданной теории. В качестве проверяемого слова выступает пара – список аксиом теории и текст алгоритма. В качестве слова-свидетеля выступает текст доказательства.

2. Доказательство теоремы $NP \ne P$ ведется от противного: предполагается, что есть полиномиально быстрый алгоритм $\operatorname{ Mt}(Aks, x)$ поиска нужного доказательства в теории с аксиомами $Aks$ для алгоритма с текстом x. В целях опровержения данной гипотезы доказательства строится алгоритм $\operatorname{AntiMt}(Aks)$, который возвращает иной результат, чем предсказывает алгоритм $\operatorname{ Mt}(Aks, \overline{\operatorname{ AntiMt }( Aks)})$.

3. Технически алгоритм $\operatorname{AntiMt}(Aks)$ строится при помощи стандартной для доказательств математической логики процедуры диагонализации. То есть, алгоритм $\operatorname{AntiMt}(Aks)$ «запускает» копию алгоритма $\operatorname{Mt}(Aks, x)$ с текстом своего – $AntiMt$ – алгоритма, ждет результат работы и возвращает в качестве собственного результата иной результат, чем выдал алгоритм $\operatorname{ Mt}(Aks, \overline{\operatorname{ AntiMt }( Aks)})$. Таким образом, алгоритм $\operatorname{Mt}(Aks, x)$ принципиально не может правильно предсказать результат работы алгоритма $\operatorname{AntiMt}(Aks)$.

Следующие 8 шагов – последовательные ограничения возможностей алгоритма $Mt$ по выдаче правильного предсказания (или возможности отказа от предсказания) результата работы алгоритма $AntiMt()$. Эти ограничения завершаться невозможностью алгоритма $Mt$ выдать правильный прогноз для $AntiMt()$, притом, что такой прогноз имеется среди доказательств соответствующей теории в пределах допустимых для доказательства размеров.

Коротко говоря, мы установим такую проверку в нашей задаче из $NP$, которая будет выявлять противоречия, которые имеют приемлемую длину вывода. И разберем те теории, в которых аксиоматизировано, что $Mt$ не может спрогнозировать $AntiMt$. И $Mt$ действительно не сможет это сделать в какой-то теории так, чтоб не придти к противоречию – которое выявляется проверкой. И не сможет сохранить полноту (отказавшись от прогноза) – потому что прогноз для $AntiMt$ будет иметь доказательство в теории и это доказательство будет приемлемой длины. Чуть подробнее:

4. Для того, чтобы противоречивый результат работы $\operatorname{Mt}(Aks, x)$ входил в противоречие с проверкой слова-свидетеля (текстом доказательства) нашей задачи из $NP$ мы сделаем предположение, что алгоритм проверки нашей задачи находит доказательство противоречия $1=0$, если таковое имеется среди всех доказательств допустимой длины для данного проверяемого слова (аксиом теории и проверяемого алгоритма). Такая гипотеза полностью согласуется с п.3 о возможности полиномиально быстрого решения произвольной единичной задачи из $NP$.

5. Когда противоречие имеется, тогда любое доказательство, чей размер не меньше доказательства противоречия – считается ложным. Таким образом, выстраивается такая конструкция нашей задачи, при которой алгоритм решения $\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}(Aks)})$ не может вернуть никакой значимый результат, если его противоречивость будет вскрыта алгоритмом проверки. А любой значимый результат для $\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}(Aks)})$ является противоречивым – по построению (п. 3) алгоритма $\operatorname{AntiMt}(Aks)$.

6. Хотя любой значимый результат для $\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}(Aks)})$ является противоречивым, но не всякое противоречие будет вскрыто алгоритмом проверки из-за его возможной чрезмерной длины. Чтобы добиться достаточно короткого доказательства противоречия, мы будем рассматривать теории, содержащие в списке аксиом аксиому: $\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}(Aks)}) = knockout$

7. Это аксиома, которая утверждает, что алгоритм $\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}(Aks)})$ может вернуть лишь незначимый результат. И данное предложение – в некотором смысле является утверждением о себе самом, потому что это аксиома, которая зависит от списка аксиом $Aks$ и при этом сама (точнее эквивалентное ему равенство) входит в список аксиом $Aks$. Данную аксиому назовём $\operatorname{DiagKnockout}(\ldots)$ и так же, как и алгоритм $\operatorname{ AntiMt }(\ldots)$, построим при помощи процедуры диагонализации.

8. В случае, если аксиома $\operatorname{DiagKnockout}(\ldots)$ расширяет непротиворечивую теорию, то алгоритм $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$ «вынужден» возвращать значимый результат. Потому что в данной теории имеется очень короткое доказательство для результата работы $\operatorname{ AntiMt }(\ldots)$ – в силу заданного аксиомой $\operatorname{DiagKnockout}(\ldots)$ результата для $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$, и в силу простой зависимости результата $\operatorname{ AntiMt }(\ldots)$ от результата работы $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$.

9. При этом, если противоречивость значимого результата $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$ будет вскрыта проверкой, то работа алгоритма $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)}) $ окажется некорректной. Но и отказаться от предсказания («согласиться» с $\operatorname{DiagKnockout}(\ldots)$) алгоритм $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$ тоже не может – иначе он не найдет короткого доказательства и не будет являться решением нашей задачи из $NP$, а аксиома $\operatorname{DiagKnockout}(\ldots)$ окажется истинной и расширенная теория из п. 8 – непротиворечивой (что гарантирует корректность доказательства).

10. Таким образом, единственная возможность алгоритма $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$ остаться корректным решением – это случай выдачи значимого результата $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$ в каждом случае, когда есть расширение $\operatorname{DiagKnockout}(\ldots)$ для непротиворечивой теории. Однако в таком случае истинным в стандартной интерпретации оказывается факт наличия противоречий всегда, когда есть аксиома $\operatorname{DiagKnockout}(\ldots)$.

11. И добавление аксиомы об этом (доказуемости отрицания $\operatorname{DiagKnockout}(\ldots)$, фактически) не сделает теорию противоречивой, но добавление $\operatorname{DiagKnockout}(\ldots)$ к такой расширенной теории сделает невозможным корректный значимый результат работы для $\operatorname{Mt}(Aks + \overline{\operatorname{DiagKnockout}(Aks)}, \overline{\operatorname{AntiMt}(\ldots)})$, что противоречит п. 9 и этим завершает доказательство.

[dmitgu]

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

Дмитрий Гуринович
Кому: Труды Московского Математического Общества
Сегодня, 7:52
1 файл
Добрый день, уважаемая редакция.
Предлагаемое доказательство (?) рассматривалось - по мере его построения - на портале dxdy.ru в теме «NP≠P. Док-во от противного-контрпример алгоритмов из NP» ( topic84426.html ) с 18 мая 2014 г. Вроде бы, там ошибок никто не находит, вроде бы получилось на хорошем уровне и не сложно - для чтения достаточно среднего знания математической логики.
Я не научный работник (так сложилось в 90-е годы, хоть и учился в МИФИ и не оставлял свой интерес к математике) - занимаюсь бухучётом. Возможно, я перескакиваю какой-то этап проверки, обращаясь в журнал. Поэтому, если не сочтете возможным рассматривать статью для журнала, то буду благодарен, если подскажете необходимый этап проверки - если он существует.
В предлагаемом виде данное доказательство я не отправлял ни в какой журнал и нигде не обнародовал - включая и интернет. Упомянутое обсуждение на dxdy.ru проходило по этапам построения и не было там сведено в итоговый текст доказательства (хоть это и легко сделать).
--
Всего доброго.
Дмитрий Гуринович
1 файл
NP_vs_P_(Dmitgu).pdf

[dmitgu]

$\text{\textbf{Предыстория}}$

Моё письмо в редакцию «Труды Московского Математического Общества» с предложенным доказательством $\mathbb{NP} \ne \mathbb{P}$ я отправил утром 11 февраля 2015 г. Ответ с отказом в публикации пришёл вечером 27 апреля 2015 г. Довольно быстро, с учётом сложности их работы. И сопутствующая переписка (очень небольшая) была дружественной и корректной по форме.

Возражения рецензента были 2-х типов:

1. По «инструментам» (вроде: правильно представлять теоремы и алгоритмы через гёделевые номера, а не то представление, которое аналогично текстам программ или по методу из «Вычислимость и логика» Дж. Булоса, Р. Джеффри)

2. По пробелам в доказательстве (вроде вопроса о том, где я даю определение $\operatorname{DiagKnockout}(Aks)$)

По обоим типам возражений у меня были ответы, но поблагодарив и чуть упомянув о своих возражениях – не стал продолжать переписку. Мне не нравился неконструктивный характер предложенного мной доказательства, и я понял, что используемый формализм надо обосновывать и пояснять, так как формализм Гёделя не подходит ко многим задачам теории алгоритмов: Вопросы логики о (не)существовании искомого ответа на бесконечности куда грубее, чем оценка времени и вопросы (не)существования ответов в полиномиальных рамках.

В процессе поиска конструктивного доказательства я нашёл ошибку в первоначальном неконструктивном доказательстве:

В своей первоначальной работе я строил задачу, в которой для произвольных алгоритмов ищется метод ускорить их вычисления. Например – сумма геометрической прогрессии может быть вычислена не только суммированием членов прогрессии, но и известной простой формулой. Чтоб «понять» (и найти) возможность ускорить вычисления, нужна какая-то теория и аксиомы $Aks$. И я построил алгоритм $\operatorname{AntiMt}()$, который предполагаемый алгоритм-«ускоритель» $\operatorname{Mt}(..., ...)$ не мог ни ускорить, ни вообще доказать его результат.

И я добавлял «диагональную» аксиому (несущую информацию о себе самой), сокращённо обозначу её $\operatorname{DiagKnockout}(Aks)$:

$\operatorname{Mt}(Aks, \overline{\operatorname{AntiMt}()}) = knockout$, означающую, что $\operatorname{Mt}(..., ...)$ не может «придумать» результат работы $\operatorname{AntiMt}()$ в рамках теории с аксиомами $Aks$.

С другой стороны, вроде бы «полный» алгоритм-решение $\operatorname{Mt}(..., ...)$ не должен возвращать признание в своей неспособности, после чего будет найден тот ответ, который не смог найти $\operatorname{Mt}(..., ...)$. Отсюда, вроде бы, верно $\neg\operatorname{DiagKnockout}(Aks)$). А там и противоречие можно получить и опровергнуть полноту $\operatorname{Mt}(..., ...)$. Но ошибка в том, что я посчитал, что $\neg\operatorname{DiagKnockout}(Aks)$ верный всегда при подстановке в непротиворечивую теорию про арифметику. Однако он не верен в случае наличия в данной теории аксиомы $\operatorname{DiagKnockout}(Aks)$, разумеется.

Это я сейчас упрощенно излагаю, а в той работе очевидные вещи были спрятаны диагонализациями и схемой аксиом. А противоречие между $\operatorname{DiagKnockout}(Aks)$ и $\neg\operatorname{DiagKnockout}(Aks)$ опровергало – вроде бы – полноту. Но опровергало – неконструктивно. Типа «есть какая-то теория, в которой $\operatorname{Mt}(..., ...)$ не найдёт ответ про AntiMt() и вернёт $knockout$ при этом. Ужасно сомнительное завершение доказательства – если уж правда есть где-то такая теория, то отчего же её не найти, не построить, не предъявить? Было бы построение конструктивным – можно было бы предметно рассмотреть построенную задачу и аккуратно проверить её на наличие ошибок.

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

$\phantom{XXX}$

$\text{\textbf{ Вот что получилось (Аннотация):}}$

Гипотеза $(\mathbb{NP} \ne \mathbb{P})$ утверждает, что найти правильный ответ в общем случае – неполиномиально (то есть – «несоизмеримо») труднее, чем проверить его. Я строил массовую задачу из класса $\mathbb{NP}$ в которой у каждого алгоритма есть не решаемая для него подзадача. Алгоритм-решение либо окажется неспособен выдать результат о своей неспособности – что будет ошибкой (информация у него есть), либо будет тянуть с поиском ответа несоизмеримо со временем проверки, либо выдаст ответ «не могу найти решение», а при этом у подзадачи будет вполне конкретное решение.

В процессе построения нужной задачи оказалось, что прежний формализм для таких построений (гёделевы номера, стандартная модель интерпретации арифметики, машина Тьюринга) – слишком «грубые». Годятся для проверок существования ответов, которые неважно ценой какого размера построений и за какое время получены. А в теории алгоритмов размеры доказательств и время их поиска имеют принципиальное значение. Поэтому формализм метаматематики был уточнён (в некоторых учебниках он использовался и раньше – я упоминаю).

А затем выяснилось, что я строю не «классическую» задачу из класса $\mathbb{NP}$, а нечто иное, но тоже – задачу из класса $\mathbb{NP}$, хотя при этом теорема Кука к этой задаче не применима («авторизуемая задача»). И оказалось, что в «классических задачах» из класса $\mathbb{NP}$ не учитывается, что задача может содержать формализованную информацию о работе алгоритмов-решений и эта информация может быть разной для разных алгоритмов-решений.

И тут обнаружилась исключительно интересная возможность (необходимая для дальнейшей работы) формализации рефлексии. Вот формализацию рефлексии я считаю самым интересным и принципиальным результатом своей работы, хотя удалось, вроде бы, доказать и неравенство $\mathbb{NP} \ne \mathbb{P}$.

Не уверен, что за время исследования в одиночку я не утратил в нём связь с реальностью, перестав замечать какие-то принципиальные ошибки. Но все построения в данной работе конструктивные, опираются на обычные методы работы с теориями первого порядка, строю даже пример действующей программы в подтверждение «Теоремы о построении алгоритма, применяемого к себе». И задача из $\mathbb{NP} \ne \mathbb{P}$, которую строю – вполне конкретная и может быть реализована хоть на уровне языка программирования (что было бы очень громоздкой работой, конечно). Всё это, надеюсь, поможет при чтении данной работы проще её понять и обнаружить не замеченные мной ошибки.

Как и в прошлый раз, хочу проверить построенные доказательства на математическом форуме, а уж если они выдержат обсуждение – будет видно, что делать дальше.

Так как ключевой идеей всей работы стали «авторизуемые задачи» из класса $\mathbb{NP}$, то именно это мне и хотелось бы обсудить в первую очередь. Идея и формализация «авторизуемых задач» изложены в разделе 6 «Задачи Кука и авторизуемые задачи из класса $\mathbb{NP}$». Если с ними можно согласиться, то в остальном доказательства простые – на мой взгляд. Хоть я и рассматривал разные нюансы – поэтому всего получилось 32 страницы формата A4 (без приложений и в формате Word – $\LaTeX$ выдаёт меньше страниц формата .pdf). Если раздел 6 годится, то будет смысл скопировать сюда всю работу – если модераторы пустят такого «слона».

Размер раздела 6 под 8 страниц, если не впишусь в 1 запись, то выложу остаток по прошествии контрольной задержки времени. Последний пункт в 6 разделе – 5.2. Вся заметка (если 40 страниц так можно назвать) с приложениями есть на ЕДРИД – «Программа Гильберта, $\mathbb{NP} \ne \mathbb{P}$, Рефлексия». Скопирую сюда оглавление, чтобы было понятно, на что делаются ссылки из раздела 6:

$\phantom{XXX}$

$\text{\textbf{ Оглавление.}}$

1. Задачи из классов $\mathbb{NP}$ и $\mathbb{P}$, $\mathbb{NP^+}$ и $\mathbb{P^+}$ – 4 страницы

2. Программа Гильберта и теория алгоритмов – 3,5 страницы

3. Сложность вопроса о $\mathbb{NP} \ne \mathbb{P}$ – 1,5 страницы

4. Предварительное замечание о программе Гильберта для теории алгоритмов – 1,5 страницы

5. Диагонализация.

$\phantom{XXX}$ 5.1. Лемма о диагонализации – 3 страницы

$\phantom{XXX}$ 5.2. Теорема о построении алгоритма, применяемого к себе – 2,5 страницы

6. Задачи Кука и авторизуемые задачи из класса $\mathbb{NP}$ – 8 страниц

7. $\mathbb{NP} \ne \mathbb{P}$ – 8,5 страниц

8. Приложения

$\phantom{XXX}$ 8.1. Первая теорема Гёделя о неполноте – 3 страницы

$\phantom{XXX}$ 8.2. Вторая теорема Гёделя о неполноте – 2,5 страницы

$\phantom{XXX}$ 8.3. Рефлексия. То, что все хотели знать о дилемме заключённого, но боялись спросить – 3,5 страницы

$\phantom{XXX}$

И по поводу обозначения – фрагмент из начала раздела 4 «Предварительное замечание о программе Гильберта для теории алгоритмов» -

На самом деле, алгоритм-решение должен получать текст программы алгоритма проверки и быть вида:

$M(\overline{L(x, y)}, x)$

Где $ \overline{L(x, y)}$ обозначает текст программы алгоритма проверки (на каком-то языке программирования), а не сам алгоритм. Именно такое обозначение для текста программ мы будем использовать и в дальнейшем.

-- 17.03.2017, 22:00 --

$\phantom{XXX}$

$\text{\textbf{Раздел 6. Задачи Кука и авторизуемые задачи из класса }} \mathbb{NP}$

$\phantom{XXX}$

1.1. В силу тезиса Чёрча любой искомый ответ получается от какого-то алгоритма. Значит, среди параметров (аргументов) задачи всегда можно задать тот, который отвечает за алгоритм, дающий ответ. Нужно лишь, чтобы задача была достаточно выразительной и была способна представлять произвольные алгоритмы.

Тогда вместо задачи $L(x, y)$ мы получим задачу $L(d, t, y)$, где аргумент $x$ разделён на 2 аргумента:

$t$ – теорема, для которой надо найти доказательство $y$;

$d$ – аргумент долга – формальное представление того алгоритма, который ищет доказательство $y$ для теоремы $t$. Самое простое формальное представление – программный код алгоритма на некотором языке программирования. Если речь о поиске доказательства без учёта ограниченных возможностей каких-либо алгоритмов-решений, то в качестве значения у аргумента долга $d$ будем задавать прочерк $\overline{-}$ и называть такое значение алгоритма долга «объективно».

1.2. В логике хорошо известны примеры вопросов, которые неразрешимы, так как для каждого алгоритма найдётся соответствующий вариант вопроса, на который алгоритм не может дать ответ. На этой базе мы и попытаемся – после серьёзной подготовки – построить полиномиально неразрешимый набор задач в классе $\mathbb{NP}$ и даже доказать $\mathbb{NP} \ne \mathbb{P}$. И да, когда корректный алгоритм даёт ответ ноль («не могу найти доказательство») – то этот ответ может быть и неполным – когда другой алгоритм доказательство найти может.

Возьмём хотя бы лемму о диагонализации (лемма и доказательство были приведены выше в подразделе 5.1 «Лемма о диагонализации») – за этой леммой был приведён пример для алгоритма-решения, который «предсказывает» поведение алгоритмов-задач (получая их текст в качестве аргумента). И там был построен «антиалгоритм»: Этот «антиалгоритм» запускает внутри себя алгоритм-решение, передавая ему в качестве аргумента свой собственный программный текст, и поступает иначе, чем «спрогнозирует» алгоритм-решение – если алгоритм-решение остановится. Но, заранее можно сказать, что алгоритм-решение не может предсказать то, какой результат выдаст его «антиалгоритм».

Из этого видно, что в задаче $L(d, t, y)$ может быть задана такая «персональная подсказка» для некого (произвольного) алгоритма-решения $M(d, t)$, что при правильном понимании алгоритмом $M(d, t)$ данной задачи он выдаст ответ $0$ («не могу найти доказательство про результат работы $AntiMt()$») за конечное время. Все нюансы мы подробно рассмотрим в своё время, а сейчас просто намечаем путь исследования.

1.3. Подход с тезисом Чёрча и обязательным наличием какого-то детерминированного алгоритма-решения (верного или не верного), дающего значение для искомого доказательства – верен в детерминированном мире, разумеется, но такова модель наших теорий. И в этом смысле для любой достаточно общей задачи, ответ для которой мы ищем, можно подразумевать не только наличие «исполнителя», дающего (или пытающегося дать) ответ, но и разные (!) правильные ответы для разных исполнителей – вообще говоря.

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

Замечу, что подобная задача «Сфинкс» $\operatorname{Sph}(d, t, y)$ с «персональной подсказкой» будет полностью соответствовать реальным фактам – если она корректно сформулирована и заявляет, что алгоритм «Эдип» $\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, t)$ не может найти доказательство $y$ для теоремы $t$ (при аргументе долга $\overline{-}$ - «объективно»), то так оно и будет. И, выдавать своё предсказание, корректно сформулированная задача «Сфинкс» будет полиномиально быстро – относительно размера «Эдипа» и теоремы $t$ – независимо от того, как долго будет работать алгоритм-решение «Эдип». Даже если «Эдип» вообще не остановится.

1.4. Работу алгоритма проверки при аргументе долга «объективно» будем называть «базовым алгоритмом проверки». Но за счет дополнительной информации о некотором (или некоторых) «избранном» алгоритме-решении внутри задачи из $\mathbb{NP}$ можно будет заранее знать о его специфических возможностях по решению заданной задачи.

Принцип независимости «базового» алгоритма проверки от алгоритмов-решений назовём «$\text{\textbf{принцип независимости}}$ $\text{\textbf{алгоритма проверки}}$». И «персональная информация» не должна вступать в противоречие с «базовой проверкой» - это тоже часть $\text{\textbf{принципа независимости}}$ $\text{\textbf{алгоритма проверки}}$. Например:

Если «персональная информация» соответствует невозможности алгоритма-решения «Эдип» найти доказательство при аргументе долга «объективно» для теоремы $t$, то необходимо, чтобы «Эдип» действительно был не способен сделать это.

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

2.1. «Персональную подсказку» для алгоритма-решения «Эдип» алгоритм «Сфинкс» будет выдавать при следующих аргументах, (пояснения в следующих двух подпунктах):

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}, t, y) = 0$

Где алгоритм долга у «Эдипа» равен «объективно» (символ прочерка), у «Сфинкса» он равен «Эдипу» с аргументом долга «объективно», теорема $t$ фиксирована, а результат 0 получается при любом доказательстве $y$ за время, полиномиальное относительно размеров |t| и $|\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, t)}|$.

И тогда корректный «Эдип» должен понять «персональную подсказку» для себя от «Сфинкса» и вернуть 0 (Ноль):

$\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, t) = 0$

2.2. Пояснение к пункту 2.1 о разных местах подстановки аргументов:

Аргумент-теорема $t$ в $\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)$ не указывается, раз он указан в «Сфинксе»:

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}, t, y)$. Не может же «Эдип» искать одно, а «Сфинкс» проверять другое. А вот аргумент долга «Эдипа» должен быть задан подстановкой в алгоритме «Эдип» - который содержится в аргументе долга «Сфинкса». Дело вот в чём:

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

И мы не будем разбивать аргумент долга на составляющие – «кто рассказывает» («Эдип»), «с точки зрения кого рассказывает» («Объективно» - в разбираемом случае), потому что тогда нам и того «с точки зрения кого» придётся разбивать на «кто» и «с точки зрения кого» и т.д. Вложенность может быть любой и нам не хватит тогда никаких аргументов.

[dmitgu]

dmitgu в сообщении #1201279 писал(а):

$\text{\textbf{Раздел 6. Задачи Кука и авторизуемые задачи из класса }} \mathbb{NP}$

Продолжение.

2.3. Пояснение к пункту 2.1 о способе подстановки аргументов в один алгоритм с получением другого алгоритма:

Алгоритм по превращению одного текста алгоритма в другой – с подставленным первым аргументом – можно изображать так: $Arg1(\overline{MyArg}, \overline{A(..., ...)})$. Мы использовали выше и продолжим использовать далее обозначения типа $B(\overline{A(..., ...)}, x), B(\overline{A(..., ...)}, ...)$ и т.п. Подразумевается, что таким образом мы используем какой-то стандартный известный способ по превращению алгоритма, зависящего от нескольких аргументов в некие другие алгоритмы – в которых часть аргументов (или даже все) исходного алгоритма уже подставлена. А можем передавать тексты алгоритмов и без подставленных аргументов, как, например $\overline{A(..., ...)}$.

Тут есть важное различие между двумя способами использования 1-го (без потери общности пусть будет 1-й) аргумента в алгоритме $A_1(x1, x2, ...)$:

2.3.1. Фиксацией некоторого значения $\overline{text1}$ в аргументе $x1$ алгоритма $A_1(x1, x2, ...)$ и превращения его в новый алгоритм $A_2(x2, x3, ...)$;

2.3.2. Использование алгоритма $A_1(x1, x2, ...)$ и его аргументов обычным образом: сначала заполняется (вне рамок инструкций и работы алгоритма $A_1(x1, x2, ...)$) информация о значениях аргументов там, где алгоритм $A_1(x1, x2, ...)$ ожидает найти эту информацию, а затем запускается алгоритм $A_1(x1, x2, ...)$.

Важное отличие между 2.3.1 и 2.3.2 в том, что в случае 2.3.1 время на присваивание переменной $x1$ значения $\overline{text1}$ является частью времени работы алгоритма $A_2(x2, x3, ...)$, а размер этой операции – включая размер текста $\overline{text1}$ - является частью размера алгоритма $A_2(x2, x3, ...)$. Поэтому в случае 2.3.1 мы не можем рассматривать значение переменной $x1$ как полученное по ссылке (когда передаётся адрес места, где находятся данные, а не сами данные – байт за байтом).

При использовании алгоритмов в духе варианта 2.3.1 будем использовать обозначение $A_1(\overline{text1}, x2, ...)$, что по виду не отличается от варианта 2.3.2 при аргументе $x1$ со значением $\overline{text1}$. Но если по контексту будет не ясно, какой из вариантов имеется в виду, то будем это специально оговаривать.

Например, на место первого аргумента внутри формулы:

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}, t, y)$

подставлен программный текст $\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}$. И в этом программном тексте подстановка в первый и второй аргументы значений $\overline{\operatorname{Sph}(..., ..., ...)}$ и $\overline{-}$ выполнены по варианту 2.3.1. И всегда для аргумента, который относится к подстановке внутри текста программы или текста логической формулы мы будем использовать вариант 2.3.1.

А если аргумент не является частью текста программы/логической формулы – может быть и вариант 2.3.1 и вариант 2.3.2. Например, в разбираемом сейчас алгоритме

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}, t, y)$

аргумент $y$ – подставляется по варианту 2.3.2. Ведь время работы данного алгоритма не зависит от размера слишком больших аргументов $y$ и поэтому аргумент $y$ – именно аргумент, размер которого и время, расходуемое на заполнение аргумента значением, не являются ни частью размера разбираемого алгоритма, ни частью времени его работы.

Более того, аргумент $y$ передаётся по ссылке, чтобы не передавать байт за байтом ненужную (при слишком большом размере значения аргумента $y$) информацию при использовании «Сфинкса».

Разницу между вариантом 2.3.1 и 2.3.2 можно практически наблюдать на примере программы из подраздела 5.2 «Теорема о построении алгоритма, применяемого к себе». Там видно, что изначально нет операции присваивания «аргументу» $x$ (хотя там аргумент представлен «готовой» переменной). Программа просто использует готовое значение из $x$ и только с этого момента отсчитывается её размер и время её работы. А в процессе исполнения процедуры диагонализации присваивание становится частью «тела» и процесса работы итоговой программы.

И в подразделе 5.1 «Лемма о диагонализации» формула $B(\operatorname{diag}(\overline{B(\operatorname{diag}(x))}))$, используемая в доказательстве Леммы, понимается в смысле варианта 2.3.1.

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

Например, пусть среди аргументов будут ещё аргументы $S$, $s$. Аргумент $S$ будет обеспечивать все нужные зависимости, а аргумент $s$ будет лишь иметь соответствующий размер, допускающий нужный размер аргумента $y$ (у нас же задача из $\mathbb{NP}$ и наибольший размер доказательства $y$ должен опираться через полином на размер каких-то других аргументов). Тогда перепишем формулу «персональной подсказки» для «Эдипа» так:

$\operatorname{Sph}(\overline{\operatorname{Oed}(\overline{\operatorname{Sph}(..., ..., ..., ..., ...)}, \overline{-}, ..., ..., ...)}, t(S), S, s, y) = 0$

А теперь можно представить данный алгоритм проверки в сокращённом виде – превратив общую исходную задачу проверки «Сфинкс» в задачу только для разбираемой персональной подсказки:

$\operatorname{Sph}_S(S, s, y) = 0$

При этом известно, что никакое доказательство не подходит и ответ получается без рассмотрения доказательства для данной частной подзадачи. То есть тут – время работы алгоритма $\operatorname{Sph}_S(S, s, y)$ не зависит от $y$ (и от размера $|y|$). И еще – между $y$ и $s$ есть соотношение – полиномиальности. Поэтому, когда «отмирает» $y$ – то «отмирает» и $s$ за ненадобностью.

Вся эта «абстрактная» подготовка в данном пункте – является более развёрнутым изложением пункта 2.3 раздела 1 «Задачи из классов $\mathbb{NP}$ и $\mathbb{P}$, $\mathbb{NP^+}$ и $\mathbb{P^+}$». А соответствующий алгоритм «Сфинкс» будет реализован в следующем разделе.

От «Эдипа» требуется решать полученную «подзадачу» на тех же принципах, что и любую задачу из класса $\mathbb{NP}$ (раз мы ищем полный алгоритм-решение, способный сводить произвольную задачу из класса $\mathbb{NP}$ к задаче из класса $\mathbb{P}$). И тогда время ответа «Эдипа» для частной задачи из «персональной подсказки» с её ограничивающим полиномом на время работы $p_{\operatorname{Sph}_S}(|S|)$ должно будет уложиться в его («Эдипа») ограничивающий алгоритм от тех же значимых аргументов – $p_{\operatorname{Oed}_S}(|S|)$. А такой ограничивающий алгоритм для времени работа «Эдипа» при ответе на «специальный вопрос» может быть неполиномиально меньше, чем у алгоритма-проверки для общей задачи – $p_{0}(|S|, |s|, ...)$.

При таком поведении «Эдипа» будет соблюдён и принцип решения задач из класса $\mathbb{NP}$: время работы алгоритма-решения не должно превышать некоторого полинома от тех значений, которые составляют ограничивающий полином для времени работы алгоритма проверки. И будет соблюдён принцип идентичности требований к решению задач – составленных подстановкой нужных зависимостей в некоторые параметры из более общей задачи – с одной стороны, а с другой стороны – те же задачи, но в которых эти же зависимости изначально считаются фиксированными (частью программы).

Обобщим полученный вывод:

Если для «персональной подсказки» алгоритма «Сфинкс» о возможностях алгоритма «Эдип» имеется ограничивающий полином $p_0(|x1|, |x2|, ...)$ на время получения «подсказки», то корректный алгоритм «Эдип», способный сводить задачи из класса $\mathbb{NP}$ к задачам из класса $\mathbb{P}$, найдёт правильный ответ (если он есть) или выдаст 0 (если «персональная подсказка» не содержит правильного ответа) за время, ограниченное некоторым полиномом от тех же аргументов $p(|x1|, |x2|, ...)$.

2.5. Для тех, кто помнит пункт 5 из раздела 1 «Задачи из классов $\mathbb{NP}$ и $\mathbb{P}$, $\mathbb{NP^+}$ и $\mathbb{P^+}$» поясню, что полиномиальность времени работы действительно является атрибутом массовой, а не единичной задачи – то есть, не все параметры (аргументы), относящиеся к «персональной подсказке» в ней могут быть зафиксированы. Уже и по этой причине нам потребовались дополнительные аргументы $S$, $s$.

3. Возникает вопрос об уместности требования от корректного «Эдипа» выявлять «подзадачи», которые пусть реально существуют внутри общей задачи, но не в «готовом виде». Но в таком нашем требовании к корректному «Эдипу» мы не нарушаем сам принцип требования к «Эдипу» – «понимать условности». Даже «готовый вид» задачи из класса $\mathbb{NP}$ – это некая условность. Мы даже информацию об алгоритме проверки «Сфинкс» передаём на каком-то языке. А это может быть Pascal, C, Prolog или даже на русском – из программы бухучёта 1С.

В сфере IT вопрос взаимодействия между программами является одним из важнейших. Написаны объёмные технологические стандарты типа com+, Corba, программы на .Net содержат в себе «манифесты» для других программ, в Интернете работает множество протоколов взаимодействия между клиентом и сервером и т.д. и т.п. И это всё – не принципиальные вопросы, а вопросы принятых условностей. Мы просто рассматриваем те алгоритмы-решения, которые «понимают» нужный нам «протокол». Если наша программа ориентирована на русский язык, то «английские» алгоритмы-решения её не поймут, но важен принцип возможности решить (или невозможности решить) со стороны той программы, которая «понимает» не принципиальные условности.

Даже «персональная подсказка» выдаётся по определённому протоколу. Как «Эдипу» выделить нужную «подзадачу»? Такой вопрос стоял бы, если бы у нас было множество «специальных задач», тогда и «Сфинкс» был бы написан иначе – и намного сложнее (в соответствии с каким-нибудь технологическим стандартом, например). Но мы будем рассматривать лишь одну «специальную задачу» – «АнтиЭдип» (для произвольного «Эдипа»). Наш протокол, который должен понимать «Эдип», можно упростить до такого: «Ищи персональную подсказку у «Сфинкса» для соответствующего тебе «АнтиЭдипа».

И ещё – по поводу того, что в общем случае для решения задачи из класса $\mathbb{NP}$ алгоритм-решение должен найти и использовать в данной задаче «персональную подсказку» для себя:

Нас ведь не удивляет, что в реальной жизни задачи, которые мы решаем – обычно поставлены персонально перед нами? Или перед нашим коллективом? Иногда их ставят люди, иногда «жизнь» или «воля божья» - кому как нравится считать. И то, что возможность решения задачи и результат решения зависят от «исполнителя» – как правило – факт. А то, что подобные факты до сих пор не были формализованы в математике – огромное упущение, которое будет исправлено в данной работе. И это гораздо более принципиальная и интересная часть работы, чем доказательство $\mathbb{NP} \ne \mathbb{P}$ – на мой взгляд.

Ещё кое-что о дополнительной «сложности» – понять, что речь «о тебе» – будет сказано в данном разделе ниже в пункте 5.1.

4.1. Заметим, что «персональная подсказка» для «Эдипа» про его возможность доказать теорему $t$ – это вовсе не ответ 0 на все доказательства, которые не может дать «Эдип». «Эдип» даёт в лучшем случае одно доказательство для заданной ему для доказывания теоремы, а может и вовсе не остановиться, и не дать ничего. «Персональные подсказки» - это обычный (при аргументе долга «объективно») результат алгоритма проверки, в котором исключены из числа корректных те доказательства, которые алгоритм-решение не может выдать по какой-то причине. Например:

Все доказательства, доказывающие данную теорему про «АнтиЭдип», кроме тех доказательств, которые «Эдип» не может доказать в силу того, что он не может предсказать поведение «Анти-Эдипа».

Персональная подсказка – это дополнительный фильтр, не пропускающий кое-что из того, что по каким-то причинам не может быть сгенерировано алгоритмом-решением.

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

Также и «персональная подсказка» для «Эдипа» - оставляет без «запрета» какие-то варианты ответов, которые для «Эдипа» исключены. Зато «персональная подсказка» может быть получена полиномиально быстро.

И для всех «обычных» (не «Эдипов» в отношении теоремы $t$) алгоритмов-решений тогда будет верно равенство:

$\operatorname{Sph}(\overline{\operatorname{NotOed}(\overline{\operatorname{Sph}(..., ..., ...)}, \overline{-}, ...)}, t, y) = \operatorname{Sph}(\overline{-}, t, y)$

4.2. Таким образом, задача из класса $\mathbb{NP}$ в общем случае подразумевает наличие у алгоритма- проверки ответов, зависящих от алгоритмов-решений (ответы, зависящие от аргумента долга с соответствующим значением). Выделение аргумента долга в отдельный аргумент – операция условная. Со времён «канторовой пары», известно, что в одно значение (в один аргумент) можно полиномиально быстро «упаковать» и «распаковать» сколько угодно много значений. Но может оказаться и так, что в задаче из $\mathbb{NP}$ не существует никаких «персональных подсказок». Тогда мы получаем «классическую» задачу из $\mathbb{NP}$ или «задачу Кука». Дадим определение:

Классические задачи из $\mathbb{NP}$ (или задачи Кука) - те, которые нельзя свести к задачам со значимым аргументом долга. Классическая задача – это задача из $\mathbb{NP}$ с незначимым аргументом долга (когда для всех алгоритмов-решений информация одинаковая).

Чтобы как-то отличить «не классические» задачи из $\mathbb{NP}$ от задач Кука, назовём неклассические задачи – «авторизуемые задачи из класса $\mathbb{NP}$». «Авторизация» - термин из сферы IT. Такое название отражает то обстоятельство, что для решения данных задач от алгоритма-решения требуется способность отличать «себя» от «не себя», требуется уметь использовать соответствующую «тебе» персональную информацию, которую может выдать при соответствующем запросе алгоритм проверки.

4.3. И задачу Кука действительно можно свести к КНФ (конъюнктивной нормальной форме), как это делается в теореме Кука. Отмечу только, что посылка теоремы Кука о наличии готовой информации об ограничивающем алгоритме (для времени работы алгоритма проверки) ошибочна. Но можно, видимо, исправить данную ошибку перебором «кандидатов» в ограничивающие алгоритмы в виде $2^n \cdot x^{2^n }$. Тогда для какого-то n будет достигнут (если это действительно задача Кука) ограничивающий алгоритм (с «перелётом» степени, скорее всего, но всё равно полиномиальный), а предыдущих $i < n$ шагов будет лишь логарифмическое количество от найденного n, что не повлияет на полиномиальность.

Разумеется, предлагаемое исправление ошибки в теореме Кука не позволяет, вообще говоря, отличить задачи из $\mathbb{NP}$ от тех, для которых ограничивающего алгоритма нет. Это и закономерно –нет отрицательного теста на остановку алгоритма и, следовательно, нет отрицательного теста на принадлежность алгоритма к классу $\mathbb{NP}$ (с наличием ограничивающего алгоритма). Что очевидно с учётом пункта 5 из раздела 1 «Задачи из классов $\mathbb{NP}$ и $\mathbb{P}$, $\mathbb{NP^+}$ и $\mathbb{P^+}$».

Если же задача является задачей Кука, то предложенный перебор n будет конечным, так как решение в каждом испытываемом случае допускает проверку при помощи алгоритма проверки – одинаковом для всех алгоритмов-решений. Однако для авторизуемых задач из $\mathbb{NP}$ дело обстоит иначе (и не только в отношении проверки).

4.4. Ясно, что превращение в КНФ – это разбор программного текста алгоритма проверки и приведение его к специальному виду – с целью некого стандартного анализа, если таковой имеется.

И разбор программного кода в общем случае необходим, потому что просто запускать алгоритм проверки при разных аргументах и таким путём найти нужное доказательство – не получится быстро: это неполиномиально долгий перебор. Поэтому выход – в анализе текста программы, а уж как делать этот анализ – через приведение к КНФ или иначе – вопрос второй.

4.5. Интересно, что в основе задачи Кука может быть и теория Пеано, которая, вроде бы, не сводится к логике высказываний. Но сама по себе проверка доказательств – действие исключительно простое – поэтому на него и опирается весь формализм – и в логике высказываний, и в сложных теориях первого порядка. Подобную проверку можно сводить к логике высказываний. Но! – когда речь идёт о свойствах алгоритмов и их возможностях по выдаче результатов – то тогда иное дело.

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

4.6. И не сводится потому, что получая алгоритм проверки – алгоритм-решение должен «понять», нет ли «персональной информации» для него. А это уже выбор – на основе терма. А к логике высказывания индивидные переменные и символы не сводятся.

Интересные подробности о необходимости выхода за рамки логики высказываний для математики можно почитать в «Основаниях математики»:

Без индивидных переменных и индивидных символов логика высказываний «… обходит стороной один очень существенный логический момент, а именно – отношение сказуемого к подлежащему, т.е. связь между субъектом и предикатом» - «Основания математики» Д. Гильберт, П. Бернайс, Том 1, Глава IV «Формализация процесса вывода II: Исчисление предикатов», Параграф 1. «Введение индивидных переменных …». И далее – использование функций с индивидными символами и переменными, любое корректное сочетания которых представляет из себя «терм» - «Основания математики» Д. Гильберт, П. Бернайс, Том 1, Глава V «Исчисление предикатов с равенством …», Параграф 1. «Расширенный формализм», п. 5 «Добавление функциональных знаков: понятие терма …».

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

Есть полиномиально быстрая информация о возможностях данного алгоритма? Да. Является ли эта задача из класса $\mathbb{NP}$? Да. Можно поставить вопрос о возможности данного алгоритма-решения выдать соответствующий ответ за время, полиномиальное от времени на получение данной «персональной подсказки»? Да. Будет ли этот ответ из класса $\mathbb{P}$ для такой подзадачи? Да.

Но при этом выяснилось, что задача имеет разные правильные решения для разных алгоритмов-решений. И это та особенность, которая не сводится к одной КНФ на все алгоритмы-решения.

[mihaild]

dmitgu в сообщении #1201279 писал(а):

Тогда вместо задачи $L(x, y)$ мы получим задачу $L(d, t, y)$,

Что такое "задача"? ($P$ и $NP$ - классы языков)

[dmitgu]

dmitgu в сообщении #1201323 писал(а):

dmitgu в сообщении #1201279

писал(а):
$\text{\textbf{Раздел 6. Задачи Кука и авторизуемые задачи из класса }} \mathbb{NP}$

Продолжение.

Окончание...

5.2. И, разумеется, у нас нет интереса к «неклассическим» задачам из $\mathbb{P}$ – мы доказываем неполноту именно относительно сведения $\mathbb{NP}$ к «обычным» задачам из $\mathbb{P}$ (или $\mathbb{NP^+}$ к $\mathbb{P^+}$) и другими здесь не интересуемся.

-- 18.03.2017, 00:04 --

mihaild в сообщении #1201329 писал(а):

Что такое "задача"? ($P$ и $NP$ - классы языков)

"Эквивалентно класс $\mathbb{NP}$ можно определить как содержащий задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга."

Из Вики, например.

[mihaild]

dmitgu в сообщении #1201338 писал(а):

"Эквивалентно класс $\mathbb{NP}$ можно определить как содержащий задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга."

Это "неформальное определение". Формально, $NP$ - это класс языков.
Если считать "задачу" и "язык" синонимами (если не считать - то приведите, пожалуйста, определение задачи), то что такое $L(x, y)$ у вас - класс задач, параметризованный двумя параметрами $x$ и $y$? Способ записи языка $\{(x, y)|L(x, y)\}$? Что-то другое?

Верно ли, что

dmitgu в сообщении #1201279 писал(а):

вместо задачи $L(x, y)$ мы получим задачу $L(d, t, y)$,

есть какое-то отображение из каких-то языков в какие-то другие?

(у вас очень много текста с как минимум нестандартными обозначениями, чтобы в нем разобраться - нужно выяснить, как они сводятся к стандартным)

Еще - вы можете найти в вашем доказательстве место, которое развалится при добавлении оракула? (существует оракул, относительно которого $P \neq NP$)

[dmitgu]

mihaild в сообщении #1201345 писал(а):

Верно ли, что dmitgu в сообщении #1201279

писал(а):
вместо задачи $L(x, y)$ мы получим задачу $L(d, t, y)$, есть какое-то отображение из каких-то языков в какие-то другие?

Ну да:

dmitgu в сообщении #1201323 писал(а):

4.2. Таким образом, задача из класса $\mathbb{NP}$ в общем случае подразумевает наличие у алгоритма- проверки ответов, зависящих от алгоритмов-решений (ответы, зависящие от аргумента долга с соответствующим значением). Выделение аргумента долга в отдельный аргумент – операция условная. Со времён «канторовой пары», известно, что в одно значение (в один аргумент) можно полиномиально быстро «упаковать» и «распаковать» сколько угодно много значений.

[mihaild]

dmitgu в сообщении #1201349 писал(а):

задача из класса $\mathbb{NP}$ в общем случае подразумевает

Задача из класса $NP$ - это множество (слов) с определенным свойством (существует недетерменированный алгоритм, разревающий это множество за полиномиальное время). Как вообще множество может что-то "подразумевать"?

Непонятно - вы предлагаете вместо задачи "существует ли выполняющий набор для данной КНФ" решать задачу "выдает ли данный алгоритм выполняющий набор для данной КНФ"?
Если да, то ограничивать ли время работы (полиномом)? Если не ограничивать, то вторая задача неразрешима (и тем самым много сложнее первой). Если ограничивать - то она очевидно решается за полиномиальное время, но чем это поможет?