Потенциально равные классы сложности без известных противоречивых релятивизаций

Какие примеры пар классов сложности и такие, что $A$ $B$

мы не знаем, является ли , и $A=B$
мы также не знаем противоречивых релятивизаций (т. е. мы не знаем оракулов и таких, что и )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Чтобы сформулировать вопрос по-другому, каковы некоторые исключения из эвристики, которая, если не удается выяснить противоречивые релятивизации, то легко решить вопрос равенства прямо?

cc.complexity-theory complexity-classes relativization Тимоти Чоу
источник

Достаточно ли будет каких-либо двух классов A и B, для которых мы не знаем, как доказать разделение оракула между A и B, чтобы ответить на ваш вопрос? (Предполагая, что А и В могут быть равны.)

Робин Котари

Вы бы приняли примеры о значениях между равенствами, а не единичными? Например, мы не знаем, подразумевает ли NP = UP, что PH разрушается, но у нас также нет оракула, в котором это значение неверно.

Джошуа Грохов

@JoshuaGrochow: Это интересно, хотя меня немного больше интересует конкретный тип примера, который я описал.

Тимоти Чоу

@ Робин Котари: Если мы не знаем оракула Q, то тем более мы не знаем оракулов P и Q, поэтому я вижу, как (A, B) удовлетворить ваши требования, но не мои, это если мы знаем что A = B, но мы не знаем оракула, который разделяет их. Я думаю, что было бы интересно увидеть пример A и B, такой, что A = B, но вполне вероятно (но не известно), что они могут быть разделены оракулом, но это не совсем то, о чем я просил.

Тимоти Чоу

Ответы:

Я думаю, что самый большой такой пример в настоящее время - это (квантовое полиномиальное время) против (полиномиальная иерархия времени). Значительные усилия были направлены на то, чтобы отделить их от оракула, но безуспешно. (Конечно, достаточно мощный оракул сделает их равными.) И самый известный результат сдерживания состоит в том, что находится в $BQP$ $PH$ $BQP$ $PP$ .

Некоторые ссылки для атак на проблему оракула: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Райан Уильямс
источник

На самом деле, самый известный результат является

, где

является (среди прочего) наибольший разрыва Определяемых sublcass из

такие , что

. Мне не известно о каком-либо интересе к классу

кроме его отношения к

и к

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$

P P

$\mathsf{PP}$ , так что в качестве уточнения это немного технический вопрос, но вы идете.

Ниль де Боудрап

Кроме того, также не известно, как отделить BQP от AM или даже QMA от AM.

Робин Котари

Известен ли оракул, отделяющий от ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Райан О'Доннелл
источник

Я почти уверен, что вопрос был задан более риторически, то есть «я думаю, что это ответ, но, возможно, есть оракул, о котором я не знаю»

Джошуа Грохов

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

Райан О'Доннелл