dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Языки логики и классы сложности. Рефлексия. NP ≠ P.


Оглавление


0. Аннотация. Использованный метод

1. «Стандартный» язык логики L. Прикладные роли языка

2. Алгоритмы-решения. Теорема о неопределимости. Утверждение AntiSol

3. Язык логики LA

4. Рефлексия на языке LA. NF ≠ F

5. Язык LS из класса NP

  5.1 Язык LS, пункты 1-5

  5.2 Язык LS, пункт 6

6. NP ≠ P на примере языка LS

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. Мои слабые способности в освоении новых для меня языков и формализмов.


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