Известно ли ?

Обратное включение очевидно, так же как и тот факт, что любой самоустраиваемый язык NP в BPP также находится в RP. Известно ли, что это также относится к несаморедуцируемым языкам NP?

cc.complexity-theory derandomization pseudorandomness bppcapnpvsrp
источник

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

RP⊆BPP $\mathbb{RP} \subseteq \mathbb{BPP}$

RP⊆NP $\mathbb{RP} \subseteq \mathbb{NP}$

BPP=RP $\mathbb{BPP} = \mathbb{RP}$

RP=NP $\mathbb{RP} = \mathbb{NP}$

BPP $\mathbb{BPP}$

NP $\mathbb{NP}$

RP $\mathbb{RP}$

BPP $\mathbb{BPP}$

chazisop

Что будет известно, что означает NP = RP. @chazisop, где вы взяли, что подразумевает BPP = RP или NP = RP?

NP⊆BPP $\mathrm{NP}\subseteq\mathrm{BPP}$

NP∩BPP=RP $\mathrm{NP}\cap\mathrm{BPP}=\mathrm{RP}$

Эмиль Йержабек

Предположим, мы знали . Затем мы можем выполнить анализ случая: - Если , то из (1) , что с известными результатами подразумевает . - Если , то из (1) , что с известными результатами подразумевает . - Если (ни один не является подмножеством другого), то мы получаем

. PS: Извините за удаление предыдущего комментария, я случайно разместил его в середине комментария и не смог отредактировать его, чтобы включить остальные случаи.

BPP∩NP⊆RP(1) $BPP \cap NP \subseteq RP (1)$

BPP⊆NP $BPP \subseteq NP$

NP⊆RP $NP \subseteq RP$

NP=RP $NP = RP$

NP⊆BPP $NP \subseteq BPP$

BPP⊆RP $BPP \subseteq RP$

BPP=RP $BPP = RP$

NP⊈BPP $NP \not\subseteq BPP$

BPP∩NP=RP $BPP \cap NP = RP$

chazisop

Вы перепутали первые два случая. Что еще более важно, в третьем, общем случае, ваш вывод идентичен предположению, поэтому весь аргумент ничего не дает. В частности, он не поддерживает неправильную заявку в вашем первом комментарии.

Эмиль Йержабек

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

chazisop

Как и в большинстве сложных вопросов, я не уверен, что будет очень полный ответ в течение очень долгого времени. Но мы можем, по крайней мере, показать, что ответ нерелятивизирующий: существует оракул, относительно которого выполняется неравенство, и один, относительно которого выполняется равенство. Довольно просто дать оракула, относительно которого классы равны: любой оракул, имеющий будет работать (например, любой оракул, относительно которого «случайность мало помогает»), так как будет любой оракул, у которого есть (например, любой оракул, относительно которого "случайность очень помогает"). Их много, поэтому я не буду вдаваться в подробности. $\mathrm{BPP} = \mathrm{RP}$ $\mathrm{NP} \subseteq \mathrm{BPP}$

Несколько сложнее, хотя и довольно просто, разработать оракула, относительно которого мы получаем . Конструкция, приведенная ниже, действительно работает немного лучше: для любой константы существует оракул, относительно которого есть язык в которого нет в . Я обрисую это ниже. $\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$ $c$ $\mathrm{coRP} \cap \mathrm{UP}$ $\mathrm{RPTIME}[2^{n^c}]$

Мы разработаем оракул который содержит строки вида , где - это битная строка, - это один бит, а - это битовая строка длиной . Мы также дадим язык который будет определяться машиной машиной следующим образом: $A$ $(x,b,z)$ $x$ $n$ $b$ $z$ $2n^c$ $L^A$ $\mathrm{coRP}$ $\mathrm{UP}$

машина, на входе , угадывает длины случайным образом , запросы , а также копии ответа. $\mathrm{coRP}$ $x$ $z$ $2|x|^c$ $(x,\mathtt{0},z)$
Машина , на входе , угадывает длины , запрашивает и копирует ответ. $\mathrm{UP}$ $x$ $z$ $2|x|^c$ $(x,\mathtt{1},z)$

Чтобы указанные выше машины действительно соответствовали их обещаниям, нам нужно, чтобы удовлетворял некоторым свойствам. Для каждого должен быть один из этих двух вариантов: $A$ $x$

Вариант 1: В лучшем случае половины выбора есть и нулевой выбора есть . (В этом случае ) $z$ $(x,\mathtt{0},z) \in A$ $z$ $(x,\mathtt{1},z) \in A$ $x \not\in L^A$
Вариант 2: Каждый выбор имеет и ровно один выбор имеет . (В этом случае ) $z$ $(x,\mathtt{0},z) \in A$ $z$ $(x,\mathtt{1},z) \in A$ $x \in L^A$

Нашей целью будет указать удовлетворяющее этим обещаниям, чтобы диагонализировался против каждой . Для того, чтобы этот короткий ответ уже был коротким, я опущу строительную технику оракула и массу неважных деталей и объясню, как диагонализировать конкретную машину. Фикс рандомизированное машина Тьюринга, и пусть будет вход , так что мы имеем полный контроль над отбором «с и » S так , что . Мы разобьем на . $A$ $L^A$ $\mathrm{RPTIME}[2^{n^c}]$ $M$ $x$ $b$ $z$ $(x,b,z) \in A$ $M$ $x$

Случай 1: Предположим, что есть способ выбрать , так что удовлетворяет первому варианту своего обещания, а имеет выбор случайности, который принимает. Тогда мы передадим этому выбору. Тогда не может одновременно выполнить обещание и отклонить . Тем не менее, . Таким образом , мы диагонализованы против . $z$ $A$ $M$ $A$ $M$ $\mathrm{RP}$ $x$ $x \not\in L^A$ $M$
Случай 2: Далее предположим, что предыдущий случай не сработал. Теперь мы покажем, что тогда можно заставить либо нарушить обещание либо отклонить какой-либо выбор удовлетворяющий второму варианту его обещания. Это диагонализует против . Мы сделаем это в два этапа: $M$ $\mathrm{RP}$ $A$ $M$
1. Покажите , что для каждого фиксированного выбора из случайных битов «с, должен отвергнуть , когда все его запросы вида в и все его запросы вида не в . $r$ $M$ $M$ $(x,\mathtt{0},z)$ $A$ $(x,\mathtt{1},z)$ $A$
2. Покажите, что мы можем перевернуть ответ на для некоторого выбора не оказывая существенного влияния на вероятность принятия $(x,\mathtt{1},z)$ $A$ $z$ $M$
Действительно, если мы начнем с с шага 1, вероятность принятия равна нулю. не совсем удовлетворяет второй вариант своего обещания, но затем мы можем перевернуть один бит, как на шаге 2, и это будет. Поскольку переключение бита приводит к тому, что вероятность принятия остается около нуля, из этого следует, что не может одновременно принять и удовлетворить обещание . $A$ $M$ $A$ $M$ $M$ $x$ $\mathrm{RP}$

Осталось обсудить два шага в случае 2:

Закрепить выбор случайных битов для . Теперь симулировать с помощью , как хаотичности и отвечать на запросы , таким образом , что и . Заметьте, что делает не более запросов. Поскольку существует вариантов выбора , мы можем исправить незапрошенные варианты выбора чтобы они , и чтобы прежнему удовлетворяли первому варианту его обещание. Поскольку мы не могли заставить Случай 2 работать для , это означает, что $r$ $M$ $M$ $r$ $(x,\mathtt{0},z) \in A$ $(x,\mathtt{1},z) \not\in A$ $M$ $2^{n^c}$ $2^{2n^c}$ $z$ $z$ $(x,\mathtt{0},z) \not\in A$ $A$ $M$ $M$ должен отказаться от всех своих случайных вариантов выбора относительно , и в частности от . Отсюда следует, что если мы выберем чтобы и для каждого выбора , то для любого выбора случайные биты , отклоняет по отношению к . $A$ $r$ $A$ $(x,\mathtt{0},z) \in A$ $(x,\mathtt{1},z) \not\in A$ $z$ $r$ $M$ $A$
Предположим, что для каждого доля случайных битов, для которых запросов равна по крайней мере . Тогда общее число запросов не менее . С другой стороны, делает не более запросов во всех своих ветвях, противоречие. Следовательно, существует возможность выбора так, чтобы доля случайных битов, для которых запросов была меньше 1/2. Следовательно, изменение значения в этой строке влияет на вероятность принятия менее чем на . $z$ $M$ $(x,\mathtt{1},z)$ $1/2$ $2^{2n^c} 2^{2^{n^c}}/2$ $M$ $2^{2^{n^c}} 2^{n^c}$ $z$ $M$ $(x,\mathtt{1},z)$ $A$ $M$ $1/2$

Эндрю Морган
источник

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

Эндрю Морган

Это может быть в обзоре Ко.

Каве

@Kaveh: Я посмотрел на этот опрос (это тот, на который вы ссылаетесь, верно?), Но я не заметил ничего, что, кажется, имеет непосредственное отношение. Большинство результатов , казалось , что они попали бы в случае доказательства

. Примечательным моментом является то, что

относительно случайного оракула, и поэтому мы получаем

относительно случайного оракула. $\mathrm{BPP} \cap \mathrm{NP} = \mathrm{RP}$

$\mathrm{P} = \mathrm{RP}$

$\mathrm{BPP} \cap \mathrm{NP} = \mathrm{RP}$

Эндрю Морган

Известно ли ?

Ответы: