Classes

Eu estava tentando entender essas aulas, mas sempre me confundia ... as perguntas são:

Qual é a relação entre e , em particular, é uma questão em aberto? $FNP$ $\#P$

Qual é a relação de e ? esta pergunta está aberta? $\oplus P$ $NP$

E o relacionamento entre e ? esta pergunta está aberta? $PH$ $P^{FNP}$

cc.complexity-theory Fayez Abdlrazaq Deab
fonte

está contido em Funcional polinomial de hierarquia, que é chamado

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$

Tayfun Pay

@ Tayfun, há algo que não faz sentido:

a primeira é a classe de função, enquanto a última é a classe de problemas de decisão.

F N P \subseteq P^{# P}

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

Fayez Abdlrazaq Deab

@ Tayfun, você poderia listar as referências que comprovam esses resultados.

Fayez Abdlrazaq Deab

Respostas:

1) está contido em , o qual é chamado de "hierarquia polinomial funcional", onde cada função em é o tempo polinomial 1-Turing reduciable para alguma função na . 2) Sabemos do teorema Valente Vazirani que . Sabemos também que . Portanto, temos $\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}$

Tayfun Pay
fonte

oi, muito obrigado, você poderia listar referências?

Fayez Abdlrazaq Deab

2) LG Valiant e V. Vazirani “NP é tão fácil quanto detectar soluções únicas” Theoretical Computer Science 47 (1986), pp. 85-93.

Tayfun Pay

1) S. Toda, O. Watanabe. "Reduções de 1-Turing em tempo polinomial de #PH para #P". Ciência da Computação Teórica. Volume 100. Páginas 205-221. 1992.

Tayfun Pay 31/08/13

cstheory.stackexchange.com/questions/6404/...

Tayfun Pay