Классы , ,

Я пытался понять эти классы, но всегда запутался ... вопросы:

Какова связь между и , в частности это открытый вопрос? $FNP$ $\#P$

Какое отношение имеют и ? этот вопрос открыт? $\oplus P$ $NP$

Как насчет отношений между и ? этот вопрос открыт? $PH$ $P^{FNP}$

cc.complexity-theory Файез Абдлразак Дееб
источник

F N P \subseteq P^{# P}

$FNP \subseteq P^{\#P}$ , и содержится в функциональной полиномиальной иерархии, которая называется .

N P \subseteq R P^{\oplus P}

$NP \subseteq RP^{\oplus P}$

P^{F N P}

$P^{FNP}$

F P H

$FPH$

Тайфун платит

@ Тайфун, есть что-то не имеющее смысла: первый класс функций, а второй класс задач решения.

F N P \subseteq P^{# P}

$FNP\subseteq P^{\#P}$

Фаез Абдлразак Диб

@ Тайфун, не могли бы вы перечислить ссылки, подтверждающие эти результаты.

Фаез Абдлразак Диб

Ответы:

1) содержится в , которая называется "функциональной иерархией полиномов", где каждая функция в имеет полиномиальное время 1-Тьюринга, приводимое к некоторой функции в . 2) Из теоремы Валианта Вазирани мы знаем, что . Мы также знаем , что . Следовательно, у нас есть . $\bf FNP$ $\bf FPH$ $\bf FPH$ $\bf \#P$
$\bf NP$ $\subseteq$ $\bf RP^{PromiseUP}$ $\bf UP$ $\subseteq$ $\bf \oplus P$ $\bf NP$ $\subseteq$ $\bf RP^{\bf \oplus P}$

Тайфун Пей
источник

привет, большое спасибо, не могли бы вы перечислить ссылки?

Файез Абдлразак Диб

2) LG Valiant & V. Vazirani «NP - это так же просто, как обнаруживать уникальные решения» Теоретическая информатика 47 (1986), с. 85-93.

Tayfun Pay

1) S. Тода, О. Ватанабе. «Сокращение 1-тьюринга за полиномиальное время с #PH до #P.» Теоретическая информатика. Том 100. Страницы 205-221. 1992.

Тайфун Пей

cstheory.stackexchange.com/questions/6404/…

Pay