0. Аннотация. Использованный метод
1. «Стандартный» язык логики L. Прикладные роли языка
2. Алгоритмы-решения. Теорема о неопределимости. Утверждение AntiSol
4. Рефлексия на языке LA. NF ≠ F
5. Язык LS из класса NP
5.2 Язык LS, пункт 6
7. О «классическом» доказательстве NP ≠ P (эвристически)
Скачать целиком в формате pdf с портала ЕДРИД:
https://edrid.ru/rid/217.015.eeea.html (ссылка на скачивание будет при развёрнутом разделе «Содержательная часть РИД» - Logic, classes of complexity, NP vs P.pdf )
Аннотация. Использованный метод.
Данная заметка – «перевод» в термины «языков» и классов их сложности с терминов «задач» предыдущей заметки на эту тему – «Программа Гильберта, NP ≠ P, Рефлексия». «Переводя» прежнюю статью, я привожу её в соответствие с той терминологией, которая, как оказалось, принята при обсуждении вопросов сложности теории алгоритмов на математическом форуме.
Примеры процедур диагонализации, алгоритмов, формирующих и работающих со своим программным кодом (с примером работающей программы), подробное рассмотрение вопросов моделей интерпретации, доказательства для некоторых известных логических фактов (включая теорему о неопределимости, теорем Гёделя и т.п.) остались в прежней заметке, где их и можно почитать - в новую заметку я их не переносил.
Заодно были «переведены» кое-какие сведения из формальной логики в термины «языков» и классов сложности теории алгоритмов. А разные теоремы о неразрешимостях в таких терминах можно переписать как теоремы о несводимости языка одного класса сложности к другому классу сложности. В частности, теорема о неопределимости записывается в виде неравенства классов NF ≠ F. А на базе этих «переведённых» результатов логики затем разбирается вопрос о принадлежности (сводимости) языка класса NP к классу P и получается доказательство для их неравенства: NP ≠ P.
На уровне формальной логики идеи доказательства о несводимости классов сложности получаются более прозрачными – из-за отсутствия полиномиальных ограничений (требуется только финитность) и за счёт того, что «переписать» давно известные и проверенные результаты в терминах теории алгоритмов проще, чем открывать что-то заново. А результат о рефлексии интересен сам по себе и на уровне формальной логики он не отягощен дополнительными построениями.
Но если интересен только вопрс о NP ≠ P, то можно начинать читать заметку сразу с пункта 6 раздела «Язык LS из класса NP». До конца раздела (4 страницы) изложено построение несколько искусственного языка LS из класса NP и то, почему его невозможно свести к классу P. То есть, фактически даётся в общих чертах доказательство неравенства NP ≠ P.
А следующий раздел (чуть больше 6 страниц) – «NP ≠ P на примере языка LS» – лишь детализирует некоторые технические подробности в доказательстве неравенства NP ≠ P. Доказательство весьма простое, как мне представляется – но желательно иметь представление о теории доказательств из математической логики и начальные представления о классах сложности P и NP из теории алгоритмов.
Четыре препятствия, которые мне было трудно преодолеть и из-за которых так долго выполнялась техническая, по сути, операция переписывания статьи с терминов задач в термины языков и классов их сложности:
1. Недоказуемость утверждения AntiSol при не остановке Sol(«AntiSol»); 2. Программный код алгоритма-решения – часть сертификата, а не слова для алгоритма проверки; 3. Правильное поведение Sol(«AntiSol») в заведомо не корректном случае (апелляция к недетерминированному алгоритму-решению); 4. Мои слабые способности в освоении новых для меня языков и формализмов.
