Большинство булевых функций не вычислимы за полиномиальное время. Некоторые варианты этого предложения можно доказать простым подсчетом.

Прежде всего, зафиксируем конечный базис $\mathscr{B}$ булевых операций, как в 1.4.1, каждая из которых действует на $\leqslant a$ битах. Затем последовательности этих операций длины $t$ порождают $O\left(\left(b n^{a}\right)^{t}\right)$ булевых функций $\mathbf{F}_{2}^{n} \rightarrow \mathbf{F}_{2}^{n}$, где $b=\operatorname{card} \mathscr{B}$. С другой стороны, число всех функций, $2^{n 2^{n}}$, растет как двойная экспонента $n$ и для больших $n$ не может быть получено за время $t$, ограниченное полиномом от $n$.

Такое же заключение делается, когда мы рассматриваем не все функции, а только перестановки: формула Стирлинга для $\operatorname{card} S_{2^{n}}=2^{n}$ ! содержит двойную экспоненту.

Вот еще одно видоизменение этой проблемы: определим временную сложность класса смежности в $S_{2^{n}}$ как минимальное число шагов, необходимое для того, чтобы вычислить некоторую перестановку в этом классе. Это понятие возникает, если мы интересуемся вычислением автоморфизмов конечной вселенной мощности $2^{n}$, которая не снабжена специфическим кодированием бинарными словами. Тогда может случиться, что подходящий выбор кодировки может существенно упростить вычисление заданной функции. Однако для большинства функций мы все равно не сможем достичь вычислимости за полиномиальное время, так как асимптотическая формула для числа классов смежности
\[
p\left(2^{n}\right) \sim \frac{\exp \left(\pi \sqrt{\frac{2}{3}\left(2^{n}-\frac{1}{24}\right)}\right)}{4 \sqrt{3}\left(2^{n}-\frac{1}{24}\right)}
\]

также показывает рост порядка двойной экспоненты.