14.1.1 Модели вычислений

Под эффективными алгоритмами всюду ниже, согласно тезису Эдмондса, мы будем понимать полиномиальные алгоритмы. Последние, в соответствии с подходом, принятым в теоретической криптографии, можно определить в двух моделях вычислений.

В однородной (uniform) модели вычислений полиномиальный алгоритм -- это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входного слова.

В неоднородной (nonuniform) модели под алгоритмом понимается семейство булевых схем . Схема имеет входов и построена, скажем для определенности, из функциональных элементов И, ИЛИ и НЕ. Без ограничения общности можно считать, что все элементы И и ИЛИ двухвходовые. Алгоритм называется полиномиальным, если существует полином, ограничивающий сверху количество элементов в схеме для всех достаточно больших .

Альтернативно, алгоритм в неоднородной модели можно определить как семейство машин Тьюринга , где работает на входных словах длины . Алгоритм называется полиномиальным, если существует полином, ограничивающий сверху время работы машины для всех достаточно больших . Это определение эквивалентно предыдущему.

Большинство определений и результатов теоретической криптографии могут быть сформулированы в обеих моделях вычислений. Всюду ниже мы будем подразумевать неоднородную модель. По-видимому, она ближе к потребностям криптографии: требуется, чтобы противник не мог найти эффективный алгоритм для каждого по отдельности достаточно большого , в то время как отсутствие у противника эффективных алгоритмов в однородной модели гарантирует, по сути, лишь высокую вычислительную сложность перехода от к .