14.1.2 Односторонние функции в теории сложности

В работах по теории сложности алгоритмов и вычислений исследуются односторонние функции, в определении которых используется традиционная мера вычислительной сложности -- сложность "в наихудшем случае". Такие функции определяются требованием несуществования полиномиальной детерминированной машины Тьюринга, решающей задачу инвертирования функции для всех входных значений. Нетрудно доказать, что функции, односторонние в смысле этого определения, существуют тогда и только тогда, когда PNP. Более того, подобную функцию легко построить из любого NP-полного языка.

Пусть  -- слово из NP-полного языка, а  -- так называемая "догадка" (witness) для . Например, для задачи ВЫПОЛНИМОСТЬ  -- это к. н. ф. булевой функции, а  -- набор значений аргументов, на котором эта функция обращается в 1. Тогда функция  -- односторонняя.

С криптографической точки зрения такие функции интереса не представляют, поскольку определение гарантирует лишь существование бесконечных последовательностей значений, на которых эти функции трудно инвертируются.