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.

complexity-theory reductions complexity-classes

— DW
źródło

Możemy mieć pewne informacje rozłożone na kilka pytań .

— Raphael

z tego pytania, np. odpowiedź „przypuszcza się, że są one odrębnymi pojęciami. rozróżnienie między koNP a NP znika wraz z redukcjami Turinga”. zwróć także uwagę na coNP ≠ NP (szeroko przypuszczalne) implikuje P ≠ NP (P jest zamknięte pod dopełnieniem). jest to związane z niektórymi głęboko otwartymi pytaniami teorii złożoności.

— vzn

Dzięki, @Raphael, przejrzałem je wszystkie i wydaje mi się, że nie odpowiadają na żadne z moich pytań.

— DW

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

P^{Σ_{i}^{P}} \subseteq {N P}^{Σ_{i}^{P}} = Σ_{i + 1}^{P} \subseteq P^{Σ_{i + 1}^{P}}

$\mathsf{P}^{\Sigma^\mathsf{P}_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}_i}= \Sigma^\mathsf{P}_{i+1}\subseteq \mathsf{P}^{\Sigma^\mathsf{P}_{i+1}}$

P^{P H} = \sum_{i \geq 0} P^{Σ_{i}^{P}} = \sum_{i \geq 0} Σ_{i}^{P} = P H

$\mathsf{P^{PH}} = \sum_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}_i} = \sum_{i\geq 0}\Sigma^\mathsf{P}_{i} = \mathsf{PH}$

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

— Kaveh
źródło