Глава 6. Сложность как цена финитизации

Третья ось: цена

До сих пор у границы финитизации было две оси. Можно ли? — диагональ (15.3) запрещает тотальный решатель. Как финитизировать? — дискриминант (15.4) и горючее (15.5) дают конечную процедуру там, где она есть. Остаётся третья:

когда вычисление уже конечно, какова его цена?

Сложность в нашей системе — это цена финитизации: структурная величина конечного процесса (число шагов L5, размер перебора). И эта величина определена именно потому, что процесс финитизирован: у безграничного процесса конечной цены нет — цена есть свойство P4-конечного бега. В этой главе сложность рассматривается на положительной, финитизированной стороне: когда вычисление или проверка уже заданы как конечный процесс, мы спрашиваем о цене — не «возможно ли», а «сколько стоит». При этом сложность не добавляет новой онтологической границы: она измеряет расстояние внутри Element-стороны — два процесса могут быть одинаково конечны, но стоить радикально разно. Поэтому она не третья master-структура рядом с диагональю и дискриминантом, а метрика положительной стороны границы.

Глава короткая намеренно: теория сложности — большая стандартная дисциплина (со своими труднорешаемостью и нижними оценками), и мы её не пересказываем. Наш вклад здесь — рамка (цена как величина финитизированной стороны), а главный её вопрос мы честно ставим, а не решаем.

Проверка дёшева, поиск — вопрос цены

Центральная асимметрия проста. Проверка предъявленного сертификата относится к Element-стороне: она задаётся конечным булевым вычислением (в классической сложностной рамке это уточняется как полиномиальная проверка в выбранной модели стоимости). Найти сертификат — перебор, и вот тут встаёт вопрос цены. Формально: задача в NP, если есть верификатор $v$, проверяющий пару вход / сертификат; в P, если есть прямой решатель. Решатель сразу даёт верификатор, игнорирующий сертификат, поэтому $\mathrm{P}\subseteq \mathrm{NP}$ следует непосредственно из определений.¹

Ключевой штрих P4: ограниченный перебор сертификатов разрешим — если задана граница на размер сертификата, перечислить конечный носитель и проверить каждый элемент. То есть вопрос сложности — не «можно ли найти» (при заданной границе перебор конечен), а насколько велика эта граница и насколько дорог перебор. Сложность — это про цену, не про возможность; возможность уже обеспечена финитизацией.

P vs NP — постановка, не решение

Отсюда главный открытый вопрос: всегда ли дешёвая проверка влечёт дешёвый поиск — то есть $\mathrm{P}=\mathrm{NP}$? В наших терминах: можно ли перебор (потенциально дорогую цену) всякий раз свернуть к прямому Element-решателю (дешёвой цене)?

Держим жёстко и честно. В нашей системе этот вопрос назван — как предикат-определение «NP сворачивается в P», — но не решён и решённым не объявляется.² Глава даёт линзу — проверка есть Element, поиск есть цена, $\mathrm{P}=\mathrm{NP}$ спрашивает, сводится ли цена поиска к цене проверки, — но не доказательство и не обзор теории сложности. Мы ставим вопрос в рамке Element / цена, и на этом честно останавливаемся.

Разбор E/R/R и что глава подготовила

Правила (L5). Цена — это величина процесса: сколько раз применено правило-шаг, насколько велик перебор. Правило конституирует не только результат, но и его стоимость.

Роли (L4). Верификатор (проверяющий) и решатель (ищущий) — две роли; их разрыв в цене и есть содержание $\mathrm{P}$ vs $\mathrm{NP}$. «Дёшево / дорого» — стоимостные статусы процесса.

{

Элементы (L1$+$P4). Конкретные входы, сертификаты, ограниченные переборы. Не элемент: безграничный поиск без бюджета — у него нет конечной цены.}

Компонент	Что фиксирует	E/R/R-категория
шаг как величина; размер перебора	конституцию и цену процесса	Правило (L5)
верификатор / решатель; «дёшево / дорого»	роли и стоимостные статусы	Роль (L4)
входы; сертификаты; ограниченный перебор	конечно-актуальные носители	Элемент (L1$+$P4)

Диагностика P4. Цена определена только на финитизированной стороне: безграничный процесс цены не имеет. Поэтому сложность — естественное продолжение границы финитизации, а не новая граница. Проверка — Element; вопрос $\mathrm{P}$ vs $\mathrm{NP}$ — открыт, и мы его только ставим.

Что глава подготовила. Третья ось границы названа: после «можно ли» (диагональ) и «как финитизировать» (дискриминант / горючее) — «сколько стоит». Машинно собран лишь каркас постановки (проверка — Element, $\mathrm{P}\subseteq \mathrm{NP}$, ограниченный перебор разрешим; $\mathrm{P}=\mathrm{NP}$ — именованный открытый вопрос), 0-аксиомно; теория сложности не пересказывается, $\mathrm{P}$ vs $\mathrm{NP}$ не решается. Дальше — финал 15.7: обе master-структуры сводятся воедино, диагональ $\oplus$ дискриминант — одна граница финитизации, и цена встаёт её третьей осью.

---

---

Часть: Часть XV. Вычисления и граница финитизации · Том: «Математика»

Навигация: ← Глава 5. Типобезопасность как fuel-финитизация · Глава 7. Синтез: одна диагональ, один дискриминант →

Footnotes

1. Машинно проверено, 0 аксиом: src/cs/PvsNP_Framing.v (4 Qed) — verifies, Decider, in_P / in_NP; verification_is_element (проверка — Element), P_subset_NP ($\mathrm{P}\subseteq \mathrm{NP}$), NP_bounded_search_decidable (ограниченный перебор сертификатов разрешим). Есть и прикладной слой сложности в src/stdlib/complexity/. ↩

2. P_collapses_NP ($\mathrm{i}{\mathrm{n}}_{\mathrm{N}}\mathrm{P}\to \mathrm{i}{\mathrm{n}}_{\mathrm{P}}$) в PvsNP_Framing.v — это определение (именованный открытый вопрос), а не теорема: ни $\mathrm{P}=\mathrm{NP}$, ни $\mathrm{P}\ne \mathrm{NP}$ не доказаны и не заявляются. ↩