Введение

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

Определение

Если для функции f, вычисляющей значение для любого экземпляра x, возможно свести в полиномиальное время вычисление f(x) к вычислению f на одном или нескольких случайных экземплярах yi, то функция является саморедуцируемой (это также известно как неадаптивное однородное саморедуцирование). При случайном саморедуцировании произвольный наихудший экземпляр x из области определения f отображается в случайное множество экземпляров y1, …, yk. Это делается таким образом, чтобы f(x) можно было вычислить за полиномиальное время, зная последовательность случайных чисел, полученную в процессе отображения, x и значения f(y1), …, f(yk). Следовательно, усредняя по индуцированному распределению на yi, средняя сложность f оказывается такой же (с точностью до полиномиальных факторов), как и сложность f в наихудшем случае при случайном выборе. Особый случай, заслуживающий внимания, – когда каждый случайный экземпляр yi распределен равномерно по всему множеству элементов в области определения f, имеющих длину |x|. В этом случае сложность f в среднем не отличается от сложности в наихудшем случае. Этот подход имеет два ключевых ограничения. Во-первых, генерация y1, …, yk выполняется неадаптивно. Это означает, что y2 выбирается до того, как станет известно значение f(y1). Во-вторых, не требуется, чтобы экземпляры y1, …, yk были равномерно распределены.

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

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

Примеры

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

Дискретный логарифм

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

Постоянный матрицы

Учитывая определение постоянного определителя матрицы, ясно, что PERM(M) для любой матрицы n x n M является многомерным многочленом степени n относительно элементов матрицы M. Вычисление постоянного определителя матрицы – сложная вычислительная задача, и было показано, что PERM является #P-полной (доказательство). Более того, возможность вычисления PERM(M) для большинства матриц подразумевает существование случайной программы, вычисляющей PERM(M) для всех матриц. Это демонстрирует, что PERM является случайным образом самосокращаемым. В дальнейшем рассматривается случай, когда элементы матрицы берутся из конечного поля Fp для некоторого простого числа p, и вся арифметика выполняется в этом поле. Пусть X – случайная матрица n x n с элементами из Fp. Поскольку все элементы любой матрицы M + kX являются линейными функциями от k, то, комбинируя эти линейные функции с многомерным многочленом степени n, вычисляющим PERM(M), мы получаем другой многочлен степени n относительно k, который мы обозначим как p(k). Очевидно, что p(0) равно постоянному определителю матрицы M.

Предположим, что мы знаем программу, которая вычисляет правильное значение PERM(A) для большинства матриц n x n с элементами из Fp, а именно, для 1 – 1/(3n) из них. Тогда с вероятностью, приблизительно равной двум третям, мы можем вычислить 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.