С. Исакова (АФТУ)
Схемная сложность обратных функций

Доклад по статье Jean-Camille Birget "On the circuit-size of inverses".
Фундаментальным в криптографии является вопрос о сложности обращения
функции. В рассматриваемой статье ключевым является несколько похожий
вопрос: "какого размера может быть обратная функция". Устанавливается связь
между такими, на первый взгляд, не очень связанными понятиями, как схемная
сложность обратных функций и классы сложности. А именно, в докладе будет
рассмотрена и доказана следующая теорема:
Если существует ограничение на размер обратной функции (точнее, если
существует полином, который для любой ациклической булевой схемы C
ограничивает размер обратной схемы C'), то полиномиальная иерархия
схлопывается до второго уровня.