Случайная самоприводимость
Случайная самосократимость ( RSR ) — это правило, согласно которому хороший алгоритм для среднего случая подразумевает хороший алгоритм для худшего случая. RSR — это способность решать все случаи проблемы, решив большую часть случаев.
Определение
[ редактировать ]Если для функции f, оценивающей любой экземпляр x, можно за полиномиальное время свести к оценке f на одном или нескольких случайных экземплярах y i , то она самосократима (это также известно как неадаптивное равномерное саморедукция ) . При случайном саморедукции произвольный экземпляр x в худшем случае в области f отображается в случайный набор экземпляров y 1 , ..., y k . Это сделано для того, чтобы f ( x ) можно было вычислить за полиномиальное время, учитывая последовательность подбрасывания монеты из отображения x и f ( y 1 ), ..., f ( y k ). Следовательно, если взять среднее значение по индуцированному распределению по y i , среднем случае сложность f в в худшем случае будет такой же (в пределах полиномиальных коэффициентов), что и рандомизированная сложность f .
Следует отметить особый случай, когда каждый случайный экземпляр y i распределяется равномерно по всему набору элементов в области f , длина которых равна | х |. В этом случае f в среднем так же сложна, как и в худшем случае. Этот подход содержит два ключевых ограничения. Сначала генерация y 1 , ..., y k выполняется неадаптивно. Это означает, что y 2 выбирается до того, как станет известно f ( y 1 ). Во-вторых, не обязательно, чтобы точки y 1 , ..., y k были распределены равномерно.
Применение в криптографических протоколах
[ редактировать ]Проблемы, требующие некоторой конфиденциальности данных (обычно криптографические проблемы ), могут использовать рандомизацию для обеспечения конфиденциальности. Фактически, единственной доказуемо безопасной криптографической системы ( одноразовый блокнот безопасность ) полностью зависит от случайности ключевых данных, подаваемых в систему.
В области криптографии используется тот факт, что некоторые теоретико-числовые функции случайно самосократимы. Сюда входит вероятностное шифрование и генерация криптостойких псевдослучайных чисел . Кроме того, схемы сокрытия экземпляров (когда слабое частное устройство использует сильное общедоступное устройство, не раскрывая его данные) легко иллюстрируются случайными самосокращениями.
Примеры
[ редактировать ]Проблема дискретного логарифма , проблема квадратичной невязкости , проблема обращения RSA и проблема вычисления перманента матрицы — все это случайные самосократимые проблемы.
Дискретный логарифм
[ редактировать ]Теорема : Дана циклическая группа G размера | Г |. Если детерминированный алгоритм A с полиномиальным временем вычисляет дискретный логарифм для доли 1/poly( n ) всех входных данных (где n = log | G | — размер входных данных), то существует алгоритм рандомизированного полиномиального времени для дискретного логарифма для всех входы.
Дан генератор g циклической группы G = { g я | 0 ≤ я < | г | } и x ∈ G дискретный логарифм x по основанию g представляет собой целое число k (0 ≤ k < | G |) с x = g к . Пусть B распределен равномерно на {0,...,| г | − 1}, то xg Б = г к + Б также распределяется равномерно на G . Поэтому хг Б не зависит от x , и его логарифм можно вычислить с вероятностью 1/poly( n ) за полиномиальное время. Тогда log g x ≡ log g xg Б - B (mod | G |) и дискретный логарифм самосократим.
Перманент матрицы
[ редактировать ]Учитывая определение перманента матрицы , ясно, что PERM ( M ) для любой n x размером n матрицы M является многомерным полиномом степени n по элементам в M . Вычисление перманента матрицы — сложная вычислительная задача: PERM было показано, что #P-полна ( доказательство ). Более того, способность вычислять PERM ( M ) для большинства матриц подразумевает существование случайной программы, которая вычисляет PERM ( M ) для всех матриц. Это демонстрирует, что PERM является случайным самосократимым. В обсуждении ниже рассматривается случай, когда элементы матрицы извлекаются из конечного поля F p для некоторого простого числа p и когда вся арифметика выполняется в этом поле.
Пусть X будет случайной n на матрицей размера n с элементами из F p . Поскольку все элементы любой матрицы M + kX являются линейными функциями от k , составив эти линейные функции с многомерным полиномом степени n , который вычисляет PERM ( M ), мы получаем другой степени n полином от k , который мы назовем p ( k ) . Ясно, что p (0) равно перманенту M .
Предположим, мы знаем программу, которая вычисляет правильное значение PERM ( A ) для большинства n матриц размером x n с элементами из F p --- в частности, 1 - 1/(3 n ) из них. Затем с вероятностью примерно две трети мы можем вычислить PERM ( M + kX ) для k = 1,2,..., n + 1. Получив эти значения n + 1, мы можем найти коэффициенты p ( k ) с использованием интерполяции (помните, что p ( k ) имеет степень n ). Как только мы точно узнаем p ( k ), мы оцениваем p (0), которое равно PERM ( M ).
Если мы это сделаем, мы рискуем ошибиться в 1/3 случаев, но, выбирая несколько случайных X и повторяя описанную выше процедуру много раз и предоставляя в качестве ответа только победителя большинства, мы можем увеличить частоту ошибок. вниз очень низко.
Последствия
[ редактировать ]- Если NP-полная задача является неадаптивно случайной саморедуцируемой, полиномиальная иерархия коллапсирует до Σ 3 .
- Если CoNP-трудная задача является случайной самоприводимой в O (log n / n ), то Σ 2 = Π 2 .
Ссылки
[ редактировать ]- М. Абади, Дж. Фейгенбаум и Дж. Килиан, О сокрытии информации от оракула , J. Comput. Сист. наук., 1989.
- С. Арора, Вокруг теоремы PCP , 1996 г.
- Дж. Фейгенбаум, Л. Фортноу, О случайной самосократимости полных множеств , 1991 г.