Как выглядят классы сложности, если мы используем сокращения Тьюринга?

Для рассуждений о таких вещах, как NP-полнота, мы обычно используем многократные сокращения (т.е. сокращения Карпа). Это приводит к таким картинкам:

(по стандартным предположениям). Я уверен, что мы все знакомы с такими вещами.

Какую картину мы получаем, если работаем с сокращениями Тьюринга (т. Е. С сокращениями Кука)? Как меняется картина?

В частности, каковы наиболее важные классы сложности и как они связаны? Я предполагаю, что играет роль, которую раньше занимали и (потому что закрыт при сокращениях Тьюринга так же, как закрыт при сокращениях Карпа); это правильно? Н Р С О Н Р Р N P N $P^{NP}$$NP$$coNP$$P^{NP}$$NP$

Так должна ли картинка теперь выглядеть как , то есть что-то вроде следующего?$P \subset P^{NP} \subset PH \subset PSPACE$

Есть ли какая-то новая последовательность, которая играет роль, которая соответствует полиномиальной иерархии? Существует ли естественная последовательность классов сложности , ,..., так что каждый класс сложности замкнут относительно сокращений Тьюринга? Каков «предел» этой последовательности: это ? Ожидается ли, что каждый класс в последовательности отличается от предыдущего? (Под «ожидаемым» я подразумеваю под правдоподобными догадками, похожими на те, в которых ожидается, что .)C 1 = P N P C 2 = ? P H P ≠ N $C_0=P$$C_1=P^{NP}$$C_2=?$$PH$$P \ne NP$

Связано: сокращение «один-один» против сокращений Тьюринга для определения NPC . В этой статье объясняется, что причина, по которой мы работаем с сокращениями Karp, заключается в том, что она дает нам более детальную, более богатую и более точную иерархию. По сути, мне интересно, как бы выглядела иерархия, если бы мы работали с сокращениями Тьюринга: как бы выглядела более грубая, менее богатая и менее точная иерархия.

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

Если полиномиальная иерархия не разрушается, все включения являются строгими.