Какие конкретные доказательства существуют для P = RP?

RP - это класс проблем, решаемых недетерминированной машиной Тьюринга, которая завершается за полиномиальное время, но также допускается односторонняя ошибка. P - это обычный класс задач, разрешимых детерминированной машиной Тьюринга, которая заканчивается за полиномиальное время.

P = RP следует из отношения в сложности схемы. Impagliazzo и Wigderson показали, что P = BPP следует, если некоторая проблема, которая может быть решена в детерминистическом экспоненциальном времени, также требует схем экспоненциального размера (обратите внимание, что P = BPP подразумевает P = RP). Возможно, из-за этих результатов у некоторых теоретиков сложности возникает ощущение, что вероятностные сокращения, вероятно, могут быть дерандомизированы.

Какие еще есть конкретные доказательства того, что P = RP?

Существование проблем в DTIME (2 ^ O (n)), которые требуют вычислений схем экспоненциального размера (что является допущением в IW), кажется правдоподобным, поскольку в противном случае мы имели бы неравномерность, ускоряющую КАЖДУЮ вычислительную проблему, которая полностью идет вразрез с нынешним мышлением, которое не видит «слишком значительного» разрыва между равномерной и неоднородной сложностью для «нормальных» задач. Это мышление исходит из того факта, что существует очень мало примеров, когда известен «неоднородный» алгоритм, который значительно лучше известного однородного (опять же, за исключением дерандомизации).

Еще одним «доказательством» является то, что относительно случайного оракула у нас есть P = BPP.

Любой конкретный результат дерандомизации свидетельствует о том, что P = BPP. Как таковые PRIMES в P (Agrawal-Kayal-Saxena'02) является одним хорошим примером. Как правило, существует несколько естественных проблем в BPP, о которых неизвестно, что они находятся в P (Полиномиальное тестирование идентичности является одним заметным исключением.)

По духу схожий с результатом, который вы упоминаете, Hastad-Impagliazzo-Levin-Luby '99 показал, что существование односторонних функций подразумевает существование псевдослучайных генераторов. Хотя это напрямую не подразумевает P = BPP, основанное на существовании односторонних функций, оно показывает, что псевдослучайные генераторы следуют из минимальных криптографических предположений. Это может рассматриваться как еще один намек на то, что BPP не более мощный, чем P.

Важно отметить, что высказывание «вероятностные сокращения могут [вероятно] быть дерандомизированы» гораздо сильнее, чем P = RP. Фактически, одна формализация понятия дерандомизации всех рандомизированных сокращений состоит в том, что относительно каждого оракула X , который, как мы знаем, является ложным (например, Хеллер. Релятивизированные полиномиальные иерархии, расширяющие два уровня, Математическая теория систем 17 (2) : 71-84, 1984 дает оракула, где Z P P = R P = E X P, который не равен P по теореме временной иерархии).$P^X=RP^X$ $X$$ZPP=RP=EXP$$P$

Вышесказанное, разумеется, говорит о дерандомизации рандомизированных сокращений Тьюринга за полиномиальное время, а не об обычном уменьшении многозначности за полиномиальное время. Я не удивлюсь, если оракул Хеллера можно адаптировать так, чтобы он давал множество X так, что для всех Y Y экспоненциально-кратно сводится к X, если Y сводится к X к RP, но без прохождения конструкции I не мог поклясться в этом.

$USAT_Q$$Q = \bot$$USAT_{\bot}$

$\phi$$\phi$$\phi$$k$$x$$\phi$$k$$x$$k$$x$$k$

$k$$k$$n$$USAT_{\bot}$$n$

$\epsilon > 0$$n^{1-\epsilon}$