Jak wyglądają klasy złożoności, jeśli zastosujemy redukcje Turinga?

Do rozumowania takich rzeczy, jak kompletność NP, zwykle stosujemy redukcje wielokrotne jeden (tj. Redukcje Karp). Prowadzi to do takich zdjęć:

(zgodnie ze standardowymi przypuszczeniami). Jestem pewien, że wszyscy znamy tego rodzaju rzeczy.

Jakie otrzymamy zdjęcie, jeśli będziemy pracować z redukcjami Turinga (tj. Redukcjami Cooka)? Jak zmienia się obraz?

$P^{NP}$$NP$$coNP$$P^{NP}$$NP$

$P \subset P^{NP} \subset PH \subset PSPACE$

$C_0=P$$C_1=P^{NP}$$C_2=?$$PH$$P \ne NP$

Powiązane: Redukcje wielokrotne vs. redukcje Turinga, aby zdefiniować NPC . W tym artykule wyjaśniono, że powodem, dla którego pracujemy nad redukcjami Karp, jest to, że zapewnia nam bardziej szczegółową, bogatszą i bardziej precyzyjną hierarchię. Zasadniczo zastanawiam się, jak wyglądałaby hierarchia, gdybyśmy pracowali z redukcjami Turinga: jak wyglądałaby grubsza, mniej bogata, mniej precyzyjna hierarchia.

$\mathsf{P}^{\Sigma^\mathsf{P}_i}$$\square^\mathsf{P}_i$$\Delta^\mathsf{P}_i$$\nabla^\mathsf{P}_i$

Jeśli hierarchia wielomianowa się nie zwija, wszystkie inkluzje są ścisłe.