против

Я знаю, что (логарифмически много обращений к оракулу NP) эквивалентно (полиномиальное количество параллельных запросов к NP oracle). Мне было интересно, "функциональные" версии этих классов также эквивалентны, то есть $\mathsf{P}^{\mathsf{NP}[\log n]}$ $\mathsf{P}^{\mathsf{NP}||}$

Если известно, что это правда, указатель будет очень полезен.

{F п}^{N п [журнал N]} знак равно {F п}^{N п | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$

cc.complexity-theory complexity-classes Jorge
источник

Ответы:

Это открытая проблема, это подразумевает среди прочего. Смотрите следующую статью: $\mathsf{NP} = \mathsf{RP}$

Алан Сельман. Таксономия классов сложности функций. Журнал компьютерных и системных наук 48 (1992), с. 357-381.

Вы можете получить его здесь: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf

Ян Йоханнсен
источник

В этой статье они используют класс

, могу ли я предположить, что

? в качестве дополнительного вопроса, есть ли прототип

-полного набора?

{F P}_{t t}^{N P}

$\mathsf{FP}^{\mathsf{NP}}_{tt}$

{F P}_{t t}^{N P} = {F P}^{N P ‖}

$\mathsf{FP}^{\mathsf{NP}}_{tt}=\mathsf{FP}^{\mathsf{NP}\|}$

{F P}^{N P ‖}

$\mathsf{FP}^{\mathsf{NP}\|}$

Хорхе

На стороне вопрос: Вы имеете в виду полные наборы для

? Единственное, что мне известно, это подсчет победителя на выборах Доджсона, см. Статью: Э. Хемаспандра, Л. Хемаспандра и Дж. Роте. Точный анализ выборов Доджсона. Система голосования Льюиса Кэрролла 1876 года затруднена для параллельного доступа к НП. J.ACM 44 (1997), с. 214-224

P^{N P | |}

$\mathsf{P}^{\mathsf{NP}||}$

Ян Йоханнсен,

{F P}^{N P [\log n]} \subseteq {F P}_{t t}^{N P} \subseteq {F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} \subseteq \mathsf{FP}_{tt}^{\mathsf{NP}} \subseteq \mathsf{FP}^{\mathsf{NP}||}$

{F P}^{N P [\log n]} = {F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$

{F P}^{N P [\log n]} = {F P}_{t t}^{N P}

$\mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}_{tt}^{\mathsf{NP}}$

Ян Йоханнсен

{F P}^{N P | |}

$\mathsf{FP}^{\mathsf{NP}||}$