Односторонние функции

Одной из наиболее важных проблем теоретической информатики является вопрос о существовании односторонних функций. Эта статья рассматривает и уточняет ряд понятий, с ним связанных. В частности, впервые приводится явное комбинаторное построение полной односторонней функции (полнота означает, что эта функция является односторонней, если таковые вообще существуют). Основные концепции содержат неожиданно много тонкостей (частично уже упоминавшихся в литературе). Здесь предлагается некоторый единый подход.