Дмитрий Леонидович Гуринович
Научный руководитель Института фундаментальной математики
1 программа Гильберта NP P Рефлексия
Описание произведения: Была использована методика Гёделя по построению такого рода тестовой задачи из класса NP, которая оказывается заведомо неразрешимой для заданного (произвольного) алгоритма-решения. При этом данная тестовая задача принадлежит классу NP, а искомый алгоритм-решение представляет из себя метод свести данную задачу к задаче из класса P. Негативный результат поиска такого метода означает, в частности, доказательство известной гипотезы теории алгоритмов NP ≠ P. В процессе построения выяснилось, что тестовая задача хоть и принадлежит классу NP, но отличается от «классических» задач из класса NP хотя бы тем, что теорема Кука к этой задаче не применима («авторизуемая задача»). И оказалось, что в «классических задачах» из класса NP не учитывается, что задача может содержать формализованную информацию для «рефлексии». Формализацию рефлексии – когда алгоритм-решение получает от задачи ту информацию о своих возможностях, которая относится именно к нему – я считаю самым интересным и принципиальным результатом данной работы, хотя удалось, вроде бы, доказать и неравенство NP ≠ P.
Ключевые слова: рефлексия, Теория алгоритмов, Программа Гильберта, Класс NP, Класс P, Отличие класса NP от класса P, Метаматематика для теории алгоритмов, Неклассические задачи из класса NP, NP vs P, Неравенство классов NP и P.
Основные результаты научного произведения:
Сформулирована метаматика для теории алгоритмов — дающая адекватную по размерам и времени обработки запись алгоритмов и математических формул — что отличается от Гёделевых номеров и стандартной интерпретации в арифметике. Выявлены те задачи в классе NP («авторизуемые задачи»), к которым не применима теорема Кука. Подобная задача оперируют с метаматематическими значениями и содержат информацию о работе алгоритмов и возможностях алгоритмов по решению данной задачи. Сложность этих задач такова, что они не могут быть сведены к логике высказываний и КНФ (конъюнктивной нормальной форме) теоремы Кука. Создан формализм, описывающий «рефлексию» — получение алгоритмом-решением от алгоритма-задачи информации, о собственной работе и возможностях алгоритма-решения, которые отличаются от информации для других алгоритмов-решений. Этим заложена возможность исследования систем, чья работа зависит от способности отличать себя и свои задачи от иных задач и субъектов. Частным случаем таких систем являемся мы сами. Построена авторизуемая задача из класса NP, в которой для любого алгоритма-решения найдётся подзадача из класса NP, которую данный алгоритм-решение не способен решить полным образом за полиномиальное (по меркам подзадачи) время своей работы. Таким образом доказано неравенство NP ≠ P. В целом — проведена работа в духе программы Гильберта — в отношении теории алгоритмов. При этом предметом рассмотрения явилась возможность полиномиально быстрого получения интересующего нас доказательств ограниченного размера или информации об отсутствии доказательства в заданных рамках. Как и в случае с программой Гильберта в логике, результат получился отрицательным.
Перспективные направления применения для дальнейших исследований и разработок: Расширение понимания класса NP, пересмотр метаматематики для теории алгоритмов, построение теории для систем с рефлексией — отличающих себя и свои задачи от иных субъектов и задач, выяснение принципиальных ограничений системы на понимание себя.
Приоритетные направления развития науки, технологий и техники в РФ: Живые системы.