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

25

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

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

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

Андраш Саламон
источник
См. Также связанный вопрос cstheory.stackexchange.com/questions/364/…
Андраш Саламон

Ответы:

13

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

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

Ноам
источник
Я подумал, что именно эту статью я упомянул в первоначальном вопросе. Что мне не хватает?
Андрас Саламон
Ой, я думаю, что я не прочитал вопрос полностью ... Причина, по которой предположение правдоподобно, состоит в том, что в противном случае у нас была бы неравномерность, ускоряющая КАЖДУЮ вычислительную проблему - что полностью противоречит нынешнему мнению, что не видит "слишком значительного" разрыва между равномерной и неоднородной сложностью для "нормальных" задач.
Ноам
1
отредактировал ответ сейчас --- все еще знакомясь с системой ...
Noam
9

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

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

Moritz
источник
6

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

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

Джошуа Грохов
источник
5

USATQQ=USAT

ϕϕϕkxϕkxkxk

kknUSATn

ϵ>0n1ϵ

Андраш Саламон
источник
PNPP=NP
@Colin: Без комментариев. :-)
Андрас Саламон