Questions marquées «complexity»

37
Est-ce que ?

Nous savons que le premier niveau de la hiérarchie polynomiale (c'est-à-dire NP et co-NP) est en PP, et que . Le théorème de Toda indique également que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Savons-nous si ? Si non, pourquoi est-ce que avec un oracle en est plus fort...