Вид РИД
Произведениe науки
Сформулирована метаматика для теории алгоритмов - дающая адекватную по размерам и времени обработки запись алгоритмов и математических формул - что отличается от Гёделевых номеров и стандартной интерпретации в арифметике. Выявлены те задачи в классе NP ("авторизуемые задачи"), к которым не применима теорема Кука. Подобная задача оперируют с метаматематическими значениями и содержат информацию о работе алгоритмов и возможностях алгоритмов по решению данной задачи. Сложность этих задач такова, что они не могут быть сведены к логике высказываний и КНФ (конъюнктивной нормальной форме) теоремы Кука. Создан формализм, описывающий "рефлексию" - получение алгоритмом-решением от алгоритма-задачи информации, о собственной работе и возможностях алгоритма-решения, которые отличаются от информации для других алгоритмов-решений. Этим заложена возможность исследования систем, чья работа зависит от способности отличать себя и свои задачи от иных задач и субъектов. Частным случаем таких систем являемся мы сами. Построена авторизуемая задача из класса NP, в которой для любого алгоритма-решения найдётся подзадача из класса NP, которую данный алгоритм-решение не способен решить полным образом за полиномиальное (по меркам подзадачи) время своей работы. Таким образом доказано неравенство NP ≠ P. В целом - проведена работа в духе программы Гильберта - в отношении теории алгоритмов. При этом предметом рассмотрения явилась возможность полиномиально быстрого получения интересующего нас доказательств ограниченного размера или информации об отсутствии доказательства в заданных рамках. Как и в случае с программой Гильберта в логике, результат получился отрицательным.