Не утверждается, что их можно как то конструктивно построить. Если бы их было возможно построить за полином, то это бы означало, что <tex>SAT_2=\Pi_2</tex> и значит <tex>P = NP</tex>.
Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n)
Это Итак, это означает , что для фиксированного если зафиксировать <tex>n</tex> , для этого фиксированного <tex>\exists{}n</tex> такая логическая схема <tex>\exists{C_n</tex>, что <tex>}\forall{} формулы \varphi{} (\varphi{} \in{} SAT |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)</tex>
<tex> \exists{C_n} \forall{\varphi{}} (\forall{x} формулы длины n \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)</tex>.
