Где именно возникает NP? Структурное переосмысление исходной формулировки Кука

В данной работе заново рассматривается исходная формулировка Кука проблемы P versus NP. Центральный вопрос состоит не в том, верно ли \(P=NP\) или \(P\neq NP\), а в том, где именно в исходной конструкции NP возникает как действительно новый вычислительный класс.

Формулировка Кука переходит от детерминированных полиномиальных вычислений ко взаимосвязи \(R(x,y)\), разрешимой за полиномиальное время, а затем — к экзистенциально расширенному виду \[L=\{x\mid \exists y\,R(x,y)\}.\] Мы утверждаем, что этот переход вводит дополнительный конечный параметр и экзистенциальный квантор, но не вводит явно новый вычислительный механизм.

Далее в работе отмечается, что выражения конечной степени, такие как \(n^x\) и \(x^n\), когда оба параметра конечны и заданы, остаются полиномиальными объектами. Следовательно, появление якобы нового класса требует дополнительного обоснования помимо простого введения параметра-сертификата.

Поэтому цель данной работы — не решить проблему P versus NP, а поставить под вопрос, появляется ли NP вообще как отдельный класс внутри исходного определения Кука.

Ключевые слова: P versus NP; NP \(_{Cook}\); формулировка Кука; полиномиальные отношения; конечные структуры; экзистенциальная верификация; сертификаты; симметрия параметров; зависимость от представления; интерпретативная сложность; основания вычислений