12.03.2017
217.015.93d1

Программа гильберта, np ≠ p, рефлексия

Вид РИД

Произведениe науки

Юридическая информация Свернуть Развернуть

Основания возникновения прав

Создано самостоятельно

Краткое описание РИД Свернуть Развернуть
Описание произведения: Была использована методика Гёделя по построению такого рода тестовой задачи из класса 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, пересмотр метаматематики для теории алгоритмов, построение теории для систем с рефлексией - отличающих себя и свои задачи от иных субъектов и задач, выяснение принципиальных ограничений системы на понимание себя.
Приоритетные направления развития науки, технологий и техники в РФ: Живые системы
Оригинал произведения Свернуть Развернуть
Содержательная часть РИД:
Источник поступления информации: Портал edrid.ru

Всего документов: 3
Всего документов: 3

Похожие РИД в системе

Защитите авторские права с едрид