dmitgu

7. О «классическом» доказательстве NP ≠ P (эвристически).

к Оглавлению

Соберу в этом заключительном разделе те сопутствующие вопросы и ответы, которые возникли по ходу написания данной статьи и показались мне заслуживающими упоминания.

1. «Забота» о псевдоинвалидах.

В классическом случае у нас только один набор для скорости работы проверки и размера доказательства, а не 2, как в разобранном случае. Но язык с 2-мя наборами «скорость проверки» + «размер доказательства» (даже с 3-мя, но мы воспользуемся 2-мя) построен. Этот построенный язык LS принадлежит классу NP и в качестве данных для этого языка от алгоритма-решения требуется использовать собственный программный код. Этот код – есть.

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

2. Если алгоритм-решение переберёт все доказательства (допустимого размера)

Если бы Sol(«AntiSol_S», S, …) мог за время p₀₊(|«AntiSol_S»|, |S|) перебрать все доказательства размером до q_S(|s|) -|a|, то доказательств для утверждения AntiSol_S не осталось бы. 

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

Но из-за того, что алгоритм Sol(«AntiSol_S», S, …) в принципе не может выдать корректный результат 1 про утверждение AntiSol_S, получается, что все доказательства, которые он «переберёт» с «готовностью» выдать 1, будут им «испорчены». Вот поэтому и получается сказанное выше «доказательств для утверждения AntiSol_S не осталось бы». 

Но это заведомо невозможно для больших S за время p₀₊(|«AntiSol_S»|, |S|) из-за неполиномиального роста q_S(|s|) - |a| относительно роста p₀₊(|«AntiSol_S»|, |S|). 

3. Док-во NP ≠ P в «классическом» варианте (эвристически)

Хотя сам классический подход в контексте вопроса об AntiSol_S при алгоритме-решении Sol(«AntiSol_S», S, s) кажется надуманным, но даже если «разрешить» алгоритму Sol(«AntiSol_S», S, s)  отвечать неполиномиально долго в сравнении со скоростью доступа к нужной информации, то есть не в пределах ограничивающего полиномиального алгоритма вида p₀₊(|t|, |S|), а с «обычным» для остальных утверждений ограничивающим алгоритмом p₁₊(|t|, |S|, |s|) , то что принципиального измениться? 

Это ведь всё равно не полный перебор, упомянутый в пункте 2 выше, а всего лишь полином, малость которого на фоне неполиномиально огромного количества возможных доказательств куда существеннее, чем разница между самими 2-мя ограничивающими алгоритмами p₀₊(|t|, |S|) и p₁₊(|t|, |S|, |s|).

Притом про утверждение AntiSol_S заранее известно, что алгоритм Sol(«AntiSol_S», S, s) не может его корректно ни подтвердить (в принципе), ни отвергнуть (а вот здесь условно – если не ограничиваться размерами доказательств). Да и сам анализ трудности решения задачи с опорой на ограниченные возможности данного (произвольного) алгоритма-решения представляется продуктивным, и проведённое доказательство для «не классического» языка из класса NP с утверждением AntiSol_S может в этом отношении оказаться полезным и при «классическом» подходе. 

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

Однако – есть сильные способы сокращения «протокола работы»: 

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

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

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

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

Да и с производными правилами вывода надо следить, чтобы время работы алгоритма проверки с ними не превышало заранее заданный ограничивающий полином. 

В общем – если пытаться дать доказательство в рамках «классического» подхода к задачам из NP (с единственным ограничивающим полиномом на время работы у алгоритма проверки), то мне не хватает в настоящий момент ни времени, ни знаний, ни сил для решения данного вопроса. И следуя примеру «разумного» алгоритма-решения Sol(…, …, …) в отношении утверждения AntiSol_S, я «выдаю ноль» в качестве результата своих недолгих попыток в этом направлении. А другие «алгоритмы» (люди и коллективы) при желании могут опереться на мои завершенные результаты в своей работе.

4. Значимость персонализации

В связи с шуточным сравнением себя с «разумным» алгоритмом Sol(…, …, …) в последнем абзаце предыдущего пункта можно снова вернуться к вопросу о рефлексии, которого мы касались в разделе «Рефлексия на языке LA. NF ≠ F». Интересно, что оперативный ответ алгоритма Sol(«AntiSol_S», S, …) о невозможности ему подтвердить истинность AntiSol_S приводит к появлению доказательства в тех же полиномиальных рамках, что и скорость ответа – то есть с размером в пределах p₀₊(|t|, |S|), а не q_S(|s|) - |a|. 

При этом оперативный ответ означает в случае результата 0 как раз то, что доказательство есть! И иначе ответить «доказательство есть» за время p₀₊(|t|, |S|) алгоритму Sol(«AntiSol_S», S, …) невозможно при достаточно больших S. 

И при достаточно больших S оперативный ответ от Sol(«AntiSol_S», S, …) = 0 (при произвольном s) позволяет другим алгоритмам убедиться в истинности утверждения AntiSol_S без неполиномиально огромных задержек, которые возникают, если Sol(«AntiSol_S», S, ss(S)) «тянет время». 

Заметим, что значения «1» и «0» мы условились использовать в качестве обозначения смыслов: «утверждение принадлежит языку LS в соответствии с полученными данными» и «принадлежность утверждения языку LS не подтверждаются полученными данными» соответственно. Но в случае с оперативным ответом Sol(«AntiSol_S», S, …)  об утверждении AntiSol_S смысл обусловлен не нами, а обстоятельствами. И результаты «1» и «0» меняют свой смысл на противоположный «нашему», если угодно. 

И этот «особенный» смысл является лишь «полуфабрикатом» для того, чтобы другие алгоритмы дали уже правильный ответ в соответствии с обычными «договоренностями» о смысле «1» и «0». В данном случае работа корректного алгоритма Sol(«AntiSol_S», S, …) выступает лишь как часть общей работы некого «коллективного алгоритма». В соответствии с тезисом Чёрча и этому «коллективному алгоритму» можно сопоставить некий вполне конкретный алгоритм, но тут мы видим как на формальном уровне проявляется «часть» и «целое», «индивидуальное» и «коллективное». Определенная работа алгоритма-решения Sol(«AntiSol_S», S, …) не может иметь смысла вне рамок более общего результата. 

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

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

5. О NP-полной задаче ДНФ

Известна теорема о наличии NP-полных задач, одной из которых (первая найденная и самая известная из них) является ДНФ – всяческие дизъюнктивные нормальные формы из логики высказываний.

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

Дело не в отдельных ДНФ, а в их комплексе, а вот их комплекс как раз и может составлять то утверждение AntiSol_S, которое неразрешимо для соответствующего ему (взятого произвольно!) алгоритма-решения Sol(«AntiSol_S», S, …). 

Поэтому «сводимость» к ДНФ – это лишь иллюзия упрощения, как мне представляется. Для того, чтобы доказать несводимость к языку класса P языка LS из класса NP, нам всё равно пришлось рассмотреть алгоритмы и воспользоваться теоремой о неопределимости – то есть решать вопрос о комплексе конкретных ДНФ, если рассматривать доказательство NP ≠ P через призму соответствующей части NP-полного языка ДНФ. 

А оперируя с алгоритмами (а не ДНФ), нам потребовалось лишь сделать кое-какие не слишком сложные построения. Видимо, это гораздо более простой путь доказательства NP ≠ P, чем пытаться решать вопрос о несводимости ДНФ к классу P «в лоб» с учётом того, что решает вопрос о истинности конкретного ДНФ не алгоритм-решение, а какая-то урезанная версия этого алгоритма, да ещё и по-разному урезанная для разных конкретных ДНФ, но при этом подчиняться все эти урезанные версии алгоритма-решения должны общему (полиномиальному) способу «урезания» для всего комплекса единичных задач в этой части из NP-полной задачи.   

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.