Funkcja jednokierunkowa
Z Wikipedii, wolnej encyclopedia
Funkcja jednokierunkowa – funkcja, która jest łatwa do wyliczenia, ale trudna do odwrócenia. „Łatwa do wyliczenia” oznacza tu, że istnieje algorytm wielomianowy, który ją wylicza. „Trudna do odwrócenia” oznacza, że żaden wielomianowy algorytm probabilistyczny nie potrafi znaleźć elementu przeciwobrazu z prawdopodobieństwem większym niż zaniedbywalne, jeśli jest wybrane losowo. Trudność dotyczy zatem średniego przypadku, a nie pesymistycznego, jak w większości problemów w teorii złożoności obliczeniowej (np. w problemach NP-trudnych).