Структурная динамика полиномиальной разрешимости: слоистые пространства состояний и полиномиальная навигируемость

В этой заметке вводится структурная и геометрическая точка зрения на разрешимость за полиномиальное время, основанная на динамике вычислительных пространств состояний. Вместо того чтобы рассматривать \(\mathrm{P}\) и \(\mathrm{NP}\) главным образом через противопоставление поиска и верификации, мы фокусируемся на эволюции, сжатии и навигируемости слоистых пространств состояний, возникающих в ходе вычисления.

Статья носит исследовательский характер и задумана как вводный шаг к более широкому структурному подходу к теории сложности. Её цель — не предложить завершённую альтернативную основу теории сложности, а разработать предварительный словарь для обсуждения механизмов глобального структурного коллапса в вычислениях.

Вычислительный формализм представляется в виде тройки \(F=(M,R,D)\), состоящей из класса вычислительных моделей, шкалы ресурсов и класса допустимых описаний. Это различение используется для отделения структур, действительно реализуемых полиномиально, от представлений, чья кажущаяся эффективность зависит от более сильных примитивных операций или альтернативных ресурсных предположений.

Центральным техническим понятием является структурная реализация языка системой состояний с расходимостью, ограниченной границей и завершением. Мы показываем, что любой язык, допускающий такую реализацию, принадлежит \(\mathrm{P}\). Подход иллюстрируется на Horn-SAT, \(2\)-SAT, двудольном паросочетании и \(3\)-SAT, с акцентом на разных формах структурного коллапса и разных препятствиях для полиномиальной навигируемости.

Получающаяся интерпретация состоит в том, что полиномиальная разрешимость — это не просто отсутствие поиска, а существование глобальных механизмов, предотвращающих неконтролируемое расширение активной вычислительной границы. Введённые здесь понятия предназначены прежде всего как организационные и программные инструменты для будущей разработки, а не как завершённая структурная теория.

Ключевые слова: вычислительная сложность; полиномиальная разрешимость; слоистые пространства состояний; полиномиальная навигируемость; структурные реализации; структурный коллапс; динамика пространства состояний; сложность доказательств; SAT; вычислительные формализмы; допустимое сжатие; робастная симуляция; слоистая динамика; рост границы; глобальная структура