По определению, подмножество $E \subset U n p u$ надлежит классу $P$, если и только если его характеристическая функция $\chi_{E}$ (равная 1 на $E$ и 0 за его пределами) принадлежит классу $P F$. Далее, $E \in U$ принадлежит классу NP тогда и только тогда, когда существуют такие подмножество $E^{\prime} \subset U \times V$, принадлежащее $P$, и полином $G$, что
\[
u \in E \Longleftrightarrow \exists(u, v) \in E^{\prime} \mathrm{c}|v| \leqslant G(|u|) .
\]

Здесь $V$ – другой мир (который может и совпадать с $U$ ). Мы будем говорить, что $E$ получено из $E^{\prime}$ с помощью полиномиально усеченной проекции.

Вышеприведенные рассуждения устанавливают смысл, в котором это определение не зависит от модели.

Ясно, что $P \subset \mathrm{NP}$. Обратное включение вряд ли выполнено. Наивный алгоритм, вычисляющий $\chi_{E}$ из $\chi_{E^{\prime}}$ поиском $v$, для которого $|v| \leqslant G(|u|)$ и $\chi_{E^{\prime}}(u, v)=1$, требует экспоненциального времени, например, когда нет такого $v$ (так как $|u|$ – функция битового размера). Конечно, если можно обрабатывать все такие $v$ параллельно, то требуемое время будет полиномиальным. Другая возможность – если у вас есть какой-либо оракул, который сообщает вам, что $u \in E$ и предоставляет подходящее $v$, то вы можете проверить это за полиномиальное время, вычисляя $\chi_{E^{\prime}}(u, v)=1$.
Заметим, что перечислимые множества могут быть описаны иначе как проекции разрешимых множеств и что в этом контексте проекции не создают неразрешимых множеств. Никому еще не удалось преобразовать диагонализационное построение перечислимых неразрешимых множеств так, чтобы установить подобный факт в области P/NP. М.Фридман ([Fr2]) предложил новый интересный подход к проблеме $\mathrm{P} / \mathrm{NP}$, основанный на модификации стратегии Громова описания групп полиномиального роста.

Давно уже известно, что эта проблема может быть сведена к проверке того, принадлежат ли $P$ некоторые очень специальные множества – NP-полные. Множество $E \subset U$ называется NP-полным, если для любого другого множества $D \subset V, D \in \mathrm{NP}$, существует такая функция $f: V \rightarrow U, f \in P F$, что $D=f^{-1}(E)$, то есть $\chi_{D}(v)=\chi_{E}(f(v))$. Приведем классическое обоснование (по С. Куку (S. Cooke), Л. Левину, P. Карпу (R.Karp)) существования NP-полных множеств. Фактически рассуждение конструктивно: оно устанавливает полиномиально вычислимое отображение, выдающее $f$ исходя из описаний $\chi_{E^{\prime}}$ и усекающего полинома $G$.

Для того, чтобы описать одну NP-полную проблему, определим бесконечное семейство булевых полиномов $b_{u}$, индексированных следующими данными, образующими объекты $u$ конструктивного мира $U$. Каждое $u$ – совокупность
\[
m \in \mathbf{N} ;\left(S_{1}, T_{1}\right), \ldots,\left(S_{N}, T_{N}\right),
\]

где $S_{i}, T_{i} \subset\{1, \ldots, m\}$, и $b_{u}$ определено как
\[
b_{u}\left(x_{1}, \ldots, x_{m}\right)=\prod_{i=1}^{N}\left(1+\prod_{k \in S_{i}}\left(1+x_{k}\right) \prod_{j \in T_{i}} x_{j}\right) .
\]

Размер (10), по определению, равен $|u|=m N$.
Положим
\[
E=\left\{u \in U \mid \exists v \in \mathbf{F}_{2}^{m}, b_{u}(v)=1\right\} .
\]

В терминах булевых истинностных значений можно сказать, что $v$ выполняет $b_{u}$, если $b_{u}(v)=1$, и $E$ называется проблемой выполнимости или $S A T$.