Дмитрий Леонидович Гуринович
Научный руководитель Института фундаментальной математики
2 Языки логики и классы сложности Рефлексия NP P
Описание произведения: Переработка предыдущей заметки на эту тему – «Программа Гильберта, NP ≠ P, Рефлексия» ( https://edrid.ru/rid/217.015.93d1.html ) на базе формализма языков и классов их сложности из теории алгоритмов. В том числе были «переведены» кое-какие сведения из формальной логики в термины «языков» и классов сложности теории алгоритмов. А разные теоремы о неразрешимостях в таких терминах можно переписать как теоремы о несводимости языка одного класса сложности к другому классу сложности. В частности, теорема о неопределимости записывается в виде неравенства классов NF ≠ F. А на базе этих «переведённых» результатов логики затем разбирается вопрос о принадлежности (сводимости) языка класса NP к классу P и получается доказательство для их неравенства: NP ≠ P.
Ключевые слова: рефлексия, Теория алгоритмов, Неравенство классов NP и P, Классы сложности.
Основные результаты научного произведения:
Неравенство NP ≠ P доказано при последовательном применении формализма, принятого в теории алгоритмов. Найдена связь между формализмами логики и теории алгоритмов, что позволяет использовать принципиальные результаты из математической логики в теории алгоритмов.
Перспективные направления применения для дальнейших исследований и разработок: Не менее интересным результатом, чем доказательство неравенства NP ≠ P представляется обнаруженное в процессе анализа возможностей работы алгоритмов обстоятельство: от корректной системы требуется «понимание» – кто она такая. И без этого понимания невозможно решение некоторых важных задач. То есть, мы вышли на формализацию такого важного для многих живых систем свойства как рефлексия. Данное обстоятельство (значимость рефлексии) обнаружилось на стыке математической логики и теории алгоритмов. Трудно переоценить важность рефлексии для жизни: Без понимания того, какие опасности грозят именно тебе и какие твои действия могут привести к катастрофе именно тебя – твоя жизнь не была бы сколько-нибудь продолжительной. И возможность формализации данного свойства (рефлексии) в математике – более принципиальна и интересна для решения многих практически важных прикладных задач и мировоззренческих вопросов, на мой взгляд, чем неравенство NF ≠ F или NP ≠ P.
Приоритетные направления развития науки, технологий и техники в РФ: Живые системы.
Впервые опубликовано 28.09.2017.