Действительно, пусть $D \in \mathrm{NP}, D \subset A$, где $A$ – некоторая вселенная. Возьмем представление $D$ как полиномиально усеченную проекцию некоторого множества $D^{\prime} \subset A \times B, D^{\prime} \in P$. Выберем нормальную, например, тьюрингову модель вычислений и рассмотрим тьюринговы протоколы вычисления $\chi_{D^{\prime}}(a, b)$ с фиксированным $a$ и переменным полиномиально ограниченным $b$. Как объяснено выше, для данного $a$ любой такой протокол может быть представлен как таблица фиксированного полиномиально ограниченного размера, строки которой – последовательные состояния вычисления. В «микроскопическом» описании позиции этой таблицы могут быть заполнены только знаками 0 или 1. Вдобавок, каждая строка таблицы снабжена описанием позиции и внутреннего состояния головки (процессора). Некоторые из заполнений правильные протоколы, другие – нет, но локальная природа тьюрингова вычисления позволяет создать такие булевы полиномы $b_{u}$ в подходящих переменных, которые на правильных протоколах принимают значение 1 , таким образом, распознавая их. Более подробные пояснения см. в [GaJ], разд. 2.6. Это определяет функцию $f$, сводя $D$ к $E$. Эта конструкция настолько непосредственна, что вычислимость $f$ за полиномиальное время получается немедленно.

Известно, что многие естественные проблемы – NP-полны, в частности (проблема распознавания) 3-SAT. Это множество определяется как подмножество $S A T$, состоящее из тех $u$, для которых $\operatorname{card}\left(S_{i} \cup T_{i}\right)=3$ для всех $i$.