Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Случайная самосокращаемость (RSR) - это правило, согласно которому хороший алгоритм для среднего случая подразумевает хороший алгоритм для наихудшего случая. RSR - это способность решать все экземпляры проблемы, решая большую часть экземпляров.

Определение [ править ]

Если для функции f оценка любого экземпляра x может быть уменьшена за полиномиальное время до оценки f на одном или нескольких случайных экземплярах y i , то она является самосокращаемой (это также известно как неадаптивное равномерное самоуменьшение ) . При случайном самоуменьшении произвольный наихудший экземпляр x в области f отображается в случайный набор экземпляров y 1 , ..., y k . Это сделано для того, чтобы f ( x ) можно было вычислить за полиномиальное время, учитывая последовательность подбрасывания монеты из отображения,x и f ( y 1 ), ..., f ( y k ). Поэтому, принимая в среднем по отношению к индуцированной распределения на у я , то в среднем случае сложность из F такой же ( в пределах полиномиальных коэффициентов) , как в худшем случае рандомизированы сложность  F .

Следует отметить особый случай, когда каждый случайный экземпляр y i равномерно распределяется по всему набору элементов в области определения f , длина которых равна | х |. В этом случае f в среднем так же сложно, как и в худшем случае. Этот подход содержит два ключевых ограничения. Сначала генерация y 1 , ..., y k выполняется неадаптивно. Это означает, что y 2 выбирается до того, как станет известно f ( y 1 ). Во-вторых, необязательно, чтобы точки y 1 , ..., y k быть равномерно распределенными.

Применение в криптографических протоколах [ править ]

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

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

Примеры [ править ]

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

Дискретный логарифм [ править ]

Теорема . Для циклической группы G размера | G |, Если детерминированный алгоритм с полиномиальным временем A вычисляет дискретный логарифм для доли 1 / poly ( n ) всех входных данных (где n = log | G | - размер входных данных), то существует алгоритм рандомизированного полиномиального времени для дискретного логарифма для всех входы.

Для образующей g циклической группы G = {  g i | 0 ≤ я <| G | }, и an x ∈ G , дискретный логарифм x по основанию g - это целое число k (0 ≤ k <| G |) с x = g k . Пусть B равномерно распределена на {0, ..., | G | - 1}, то xg B = g k + B также равномерно распределен на G. Следовательно, xg B не зависит от x , и его логарифм может быть вычислен с вероятностью 1 / poly ( n ) за полиномиальное время. Тогда log g x ≡ log g xg B - B (mod | G |) и дискретный логарифм самоприводится.

Перманент матрицы [ править ]

Учитывая определение постоянной матрицы, то ясно , что PERM ( M ) для любого ˝n˝ матрицы с размерностью п матрицы M является многомерным многочленом степени п над записями в M . Вычисление перманента матрицы - сложная вычислительная задача: PERM оказался # P-полным ( доказательство ). Более того, способность вычислять PERM ( M ) для большинства матриц подразумевает существование случайной программы, которая вычисляет PERM ( M ) для всех матриц. Это демонстрирует, чтоPERM является случайным самовосстанавливающимся. Обсуждение ниже рассматривает случай, когда элементы матрицы взяты из конечного поля F p для некоторого простого p , и когда вся арифметика выполняется в этом поле.

Пусть X случайный п матрицы с размерностью п матрица с элементами из F р . Поскольку все элементы любой матрицы M + kX являются линейными функциями от k , составив эти линейные функции с многомерным многочленом степени n, который вычисляет PERM ( M ), мы получим еще один многочлен степени n от k , который мы назовем p ( k ) . Очевидно, что р (0) равно перманента М .

Предположим , что мы знаем программу , которая вычисляет правильное значение PERM ( A ) для большинства п матрицу с размерностью п матриц с элементами из F р --- в частности, 1 - 1 / (3 н ) из них. Затем с вероятностью примерно две трети мы можем вычислить PERM ( M + kX ) для k = 1,2, ..., n + 1. Получив эти n + 1 значения, мы можем найти коэффициенты при p ( k ) с помощью интерполяции (помните, что p ( k ) имеет степеньп ). Как только мы точно знаем p ( k ), мы вычисляем p (0), который равен PERM ( M ).

Если мы это сделаем, мы рискуем ошибиться в 1/3 случаев, но, выбирая несколько случайных X и повторяя описанную выше процедуру много раз, и предоставляя в качестве ответа только большинство победителей, мы можем повысить частоту ошибок. вниз очень низко.

Последствия [ править ]

  • Если NP-полная задача является неадаптивно случайной самоприводимой, иерархия полиномов схлопывается до Σ 3 .
  • Если CoNP-сложная задача является случайной самовосстанавливающейся в O (log n / n ), то Σ 2 = Π 2 .

Ссылки [ править ]