Вычислительно необратимая функция

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

Что означает термин

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

Как устроено

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

Вычислительную необратимость не следует смешивать с математической необратимостью. Для обычной обратимой функции важно, чтобы каждое значение достигалось только в одной точке области определения. Вычислительно необратимая функция может рассматриваться отдельно по сложности прямого и обратного вычислений.

Где применяется

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