, , cours

J'essayais de comprendre ces cours mais je me suis toujours embrouillé ... les questions sont:

Quelle est la relation entre et , en particulier est-ce une question ouverte? $FNP$ $\#P$

Quelle est la relation de et ? cette question est-elle ouverte? $\oplus P$ $NP$

Qu'en est-il de la relation entre et ? cette question est-elle ouverte? $PH$ $P^{FNP}$

cc.complexity-theory Fayez Abdlrazaq Deab
la source

F N P \subseteq P^{# P}

$FNP \subseteq P^{\#P}$ , et est contenu dans la hiérarchie polynomiale fonctionnelle, appelée .

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, il y a quelque chose qui n'a pas de sens: le premier est la classe de fonction tandis que le dernier est la classe des problèmes de décision.

F N P \subseteq P^{# P}

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

Fayez Abdlrazaq Deab

@Tayfun pourriez-vous s'il vous plaît énumérer les références prouvant ces résultats.

Fayez Abdlrazaq Deab

Réponses:

1) est contenu dans , qui est appelé la "hiérarchie polynomiale fonctionnelle", où chaque fonction dans est un temps polynomial 1-Turing réductible à une fonction dans . 2) Nous savons par le théorème de Valiant Vazirani que . Nous savons aussi que . Par conséquent, nous avons . $\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
la source

salut, merci beaucoup, pourriez-vous énumérer des références?

Fayez Abdlrazaq Deab

2) LG Valiant & V. Vazirani «NP est aussi simple que de détecter des solutions uniques» Theoretical Computer Science 47 (1986) pp. 85-93.

Tayfun Pay

1) S. Toda, O. Watanabe. "Réductions 1-Turing en temps polynomial de #PH à #P." Informatique théorique. Volume 100. Pages 205-221. 1992.

Tayfun Pay du

cstheory.stackexchange.com/questions/6404/…

Tayfun Pay