Функция $f\colon X\to\{0,1\}^*$, где $X\subseteq\{0,1\}^*$, называется полиномиально вычислимой, если существует полиномиальный детерминированный алгоритм $\mathcal E$ такой, что $\mathcal E(x)=f(x)$ для любого $x\in X$.