Осень 1956 года. Курт Гёдель выводит на листе бумаги вопрос, обращённый к умирающему Джону фон Нейману: можно ли проверить выполнимость булевой формулы быстрее, чем полным перебором? Ответ придёт через 69 лет — и окажется укусом логического уробороса, мифического змея, поедающего собственный хвост.

Змей рождается из случайности. Ансамбль K-SAT-формул (задач о выполнимости логической формулы) строится так: каждая переменная — узел, каждый дизъюнкт (логическое «ИЛИ» переменных или их отрицаний) — звено цепи. При ширине звена K ~ 20 для миллиона переменных (N=$10^6$) и критической плотности дизъюнктов число выполняющих подстановок подчиняется распределению Пуассона. Это статистика редких событий — как дождевые капли на тротуаре. С вероятностью около 37% возникают формулы с ровно одним решением. И вот решающий шаг: авторы заменяют один безобидный дизъюнкт «убийственным» клозом, запрещающим это единственное решение. Формула-близнец, внешне неотличимая, становится невыполнимой. Змей проглотил свой хвост.

Локальный наблюдатель, видящий лишь осколок формулы (до $N^c$ дизъюнктов, c<1), не способен отличить выполнимого змея от его мёртвого двойника. Это слепота по необходимости. Структурная неприводимость переводит вычислительную трудность в разряд информационного дефицита. На языке алгоритмической информации всякий алгоритм, ограниченный окном в t = $N^{1-δ}$ дизъюнктов, обречён иметь колмогоровскую сложность $$ K(A) \ge \Omega($N^{1-\delta}$) $$ Минимальная длина программы в битах экспоненциально велика. Отсюда — ширинный барьер для резолюций: любое доказательство невыполнимости разбухает до exp(Ω($N^{1-2δ}$)) шагов. При δ → 0+ это число стремится к $2^N$ — барьеру, предписанному Гипотезой сильного экспоненциального времени (SETH, гипотеза о невозможности субэкспоненциального решения SAT). Хвост уробороса сомкнулся: локальная слепота требует экспоненциального прозрения.

Эта работа переопределяет природу сложности. Классический вопрос P ≠ NP, сформулированный в терминах классов языков, уступает место более тонкому различению: разрыв между истиной и доказуемостью внутри конечной системы. Сложность оказывается не свойством задачи, а логической необходимостью. Это объясняет провал десятилетий атак: сама постановка вопроса выходит за горизонт локального синтаксического вывода. Для квантовых вычислений предел абсолютен — в отличие от алгоритма Шора для факторизации, эксплуатирующего скрытую периодичность, SAT-задача лишена такой лазейки. Современные нейросетевые модели, оперирующие локальными статистическими сжатиями, упираются в ту же стену информационной недостаточности. Точное численное моделирование таких формул требует экспоненциальных ресурсов. Коллективное поведение дизъюнктов в ансамбле порождает фазовый переход, неподвластный локальному анализу.

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