P vs NP: lower bounds, transfer barriers и статус задачи

Статус на 30 августа 2026 года: P vs NP остается нерешенной Millennium Prize Problem. Clay Mathematics Institute по-прежнему относит ее к шести нерешенным задачам. Этот текст — исследовательский релиз AlgoCosmos, а не заявление о доказательстве P≠NP.

Что нового в Release R2

R2 объединяет restricted lower bounds, transfer no-go theorems и новые solver-backed проверки в одну строгую карту. После R1 программа стала жестче в двух местах: auxiliary-variable elimination теперь рассматривается как отдельная модельная операция с собственным cost ledger, а любые переносы hardness обязаны проходить exact correspondence/parameter-preservation audit до повышения статуса claim.

Внутренний Target-Bridge Closure текущей research-программы на последнем синхронизированном M144/R4 pass: 357/1000. Это не вероятность и не «35.7% решения»; это только ledger текущих доказанных/открытых мостов выбранной программы.

Главное за минуту

Класс P содержит задачи, решаемые за polynomial time. Класс NP содержит задачи, где положительный ответ имеет polynomial-size certificate, проверяемый за polynomial time. Известно P ⊆ NP; неизвестно, является ли включение строгим.

Внутренняя программа AlgoCosmos прошла важную коррекцию. Старые count/entropy аргументы были уничтожены контрпримерами. Вместо них используется typed lower-bound pipeline:

\boxed{ \text{model} \to\text{structural obstruction} \to\text{exact lower bound} \to\text{stronger-model attack} \to\text{transfer theorem} \to\text{NP-complete target} }

На сегодня доказаны реальные restricted lower bounds и несколько сильных no-go теорем о переносе между моделями. Но ни один из этих результатов не дает superpolynomial lower bound для SAT против всех polynomial-time algorithms.

1. Точная постановка

Язык L лежит в P, если существует deterministic Turing machine, решающая membership за время n^{O(1)}.

Язык L лежит в NP, если существует polynomial-time verifier V и polynomial p такие, что

x\in L \iff \exists y,\ |y|\le p(|x|),\ V(x,y)=1.

Cook–Levin theorem делает SAT NP-complete. Поэтому задача P vs NP в нужном направлении может быть закрыта, например, theorem-level lower bound, исключающим polynomial-time SAT algorithm.

Restricted representation lower bound сам по себе этого не делает.

2. Первый falsifier: размер множества решений не определяет сложность

Для

f(x)=x_1, \qquad g(x)=x_1\oplus\cdots\oplus x_n

число положительных входов одинаково:

|f^{-1}(1)|=|g^{-1}(1)|=2^{n-1}.

Но deterministic decision-tree complexity различается:

D(f)=1, \qquad D(g)=n.

Следовательно, count-based entropy не может быть универсальным lower-bound invariant без дополнительной structural lemma.

Извлеченный принцип: counting работает только после доказательства максимального покрытия одним допустимым atom модели.

3. Exact theorem: DNF parity lower bound

Для

PARITY_n=x_1\oplus\cdots\oplus x_n

каждый непротиворечивый DNF-term, который не ошибается на parity, обязан фиксировать все n переменных. Если хотя бы одна переменная свободна, ее flip сохраняет term, но меняет parity.

Значит один valid term покрывает максимум один positive assignment. Положительных assignments ровно 2^{n-1}. Поэтому

\boxed{DNFsize(PARITY_n)=2^{n-1}.}

Это настоящий exponential lower bound — но только в модели DNF.

4. Stronger-model adversary: та же функция имеет линейный circuit

Используем identity

a\oplus b=(a\lor b)\land\neg(a\land b).

Итерация XOR дает ordinary fan-in-two Boolean circuit size

\le 4(n-1).

Поэтому для одной и той же функции:

DNFsize(PARITY_n)=2^{n-1}, \qquad CircuitSize(PARITY_n)=O(n).

Это theorem-level firewall: restricted hardness может полностью исчезнуть в более сильной модели.

5. Generic circuit→DNF transfer невозможен

Предположим, существует exact universal compiler, переводящий любой ordinary Boolean circuit C в эквивалентную DNF polynomial output size. Подадим на него linear-size parity circuit. Результат обязан быть DNF для parity, а ее размер не меньше 2^{n-1}.

Следовательно:

\boxed{\text{любой exact general-circuit→DNF compiler имеет exponential worst-case blow-up.}}

Значит lower bound в DNF нельзя переносить на general circuits через generic efficient compilation.

6. CNF дает тот же урок

Для parity любой non-tautological implicate в CNF обязан содержать все n input variables. Иначе omitted variable можно flip, сохранив falsification clause и изменив parity.

Отсюда

\boxed{CNFsize(PARITY_n)=2^{n-1}.}

Но Tseitin encoding XOR-chain с auxiliary variables имеет linear size и удовлетворяет

PARITY_n(x)=1 \iff \exists z\;F_n(x,z).

То есть удаление auxiliary variables может иметь exponential cost.

Вывод: extended formulations и existential projection нельзя молча отождествлять с same-variable representation.

7. Exact correspondence before transfer

Cycles 028–031 усилили transfer firewall. Если между двумя моделями заявляется exact correspondence, необходимо отдельно доказать:

semantic equivalence;
direction of simulation;
parameter blow-up;
auxiliary-variable cost;
whether the correspondence preserves the exact hardness quantity.

Даже красивый bijection/combinatorial interpretation не получает hardness-transfer credit, пока этот ledger не закрыт.

8. Что проверяет Orchestra

Длинные finite-search и logical checks маршрутизируются через специализированный стек:

Z3 — SAT/SMT equivalence, implicate search, collision/falsifier checks;
PySAT/independent SAT layer — independent finite-check path where useful;
Lean — небольшие proof kernels для transfer lemmas;
Python — glue и генерация instances, но не основной proof engine.

Z3 уже использован в Cycles 029–031 для formula-depth/CNF calibration; Lean — для независимых formal kernels. Эти проверки повышают evidence maturity, но не заменяют mathematical theorem.

9. Барьеры, которые нельзя обходить риторикой

Любая P vs NP программа обязана отдельно проходить:

relativization;
Natural Proofs;
algebrization;
model-transfer audit;
parameter-loss ledger;
auxiliary-variable/projection audit;
target-specificity gate.

Упоминание названия barrier не считается прохождением. Нужно показать, почему конкретный mechanism не попадает под hypotheses barrier или какое новое ingredient используется.

10. Что уже закрыто внутри программы

Текущий research ledger имеет следующие сильные локальные результаты:

entropy/count proxy как universal invariant — FALSIFIED;
exact exponential parity lower bound в DNF — PROVED;
exact exponential parity lower bound в same-variable CNF — PROVED;
ordinary parity circuit O(n) — PROVED;
generic polynomial exact circuit→DNF compiler — FALSIFIED;
cheap elimination Tseitin auxiliaries to same-variable CNF — FALSIFIED in worst case;
exact correspondence must preserve model and parameter costs — MANDATORY / strengthened.

11. Главный незакрытый мост

Все сильные результаты выше остаются restricted-model mathematics. Главный terminal bridge имеет вид

\boxed{ \text{target-specific structure} \to \text{superpolynomial hardness in a model strong enough for SAT} \to P\ne NP. }

Сейчас отсутствует theorem, который переносит уже доказанную restricted hardness на SAT/general polynomial-time computation с контролируемыми параметрами.

12. Что этот релиз НЕ доказывает

Он не доказывает:

P≠NP;
superpolynomial general-circuit lower bound для SAT;
lower bound против всех polynomial-time algorithms;
что parity сама является NP-complete target;
что один из известных barriers уже преодолен.

13. Текущий следующий шаг

Следующий theorem-sized шаг должен быть target-specific transfer: взять реальную NP-complete family, зафиксировать exact reduction/model interface и доказать, что выбранный hardness invariant сохраняется с parameter loss, недостаточным для collapse lower bound.

Orchestra rule для этой ветки:

\boxed{ \text{transfer ledger before lower bound escalation}.}

Источники

Clay Mathematics Institute — P vs NP, official Millennium Problem description.
S. Cook — The Complexity of Theorem-Proving Procedures.
L. Levin — NP-completeness foundations.
Baker, Gill, Solovay — relativization.
Razborov, Rudich — Natural Proofs.
Aaronson, Wigderson — algebrization.
Karchmer–Wigderson — communication/formula-depth correspondence.
AlgoCosmos canonical artifacts: Cycles 001, 007, 020, 028–031.

Scientific status: OPEN. Release R2 улучшает lower-bound architecture и falsifiability, но не является решением Millennium Prize Problem.