Seperti apakah kelas kompleksitas, jika kita menggunakan pengurangan Turing?

Untuk alasan tentang hal-hal seperti kelengkapan NP, kami biasanya menggunakan banyak-satu pengurangan (yaitu, pengurangan Karp). Ini mengarah ke gambar seperti ini:

(di bawah dugaan standar). Saya yakin kita semua akrab dengan hal semacam ini.

Gambar apa yang kita dapatkan, jika kita bekerja dengan pengurangan Turing (yaitu, pengurangan Cook)? Bagaimana gambar berubah?

Secara khusus, kelas kompleksitas apa yang paling penting, dan bagaimana hubungannya? Saya menduga bahwa memainkan peran yang dulu diambil oleh dan (karena ditutup di bawah pengurangan Turing dengan cara yang sama seperti$P^{NP}$$NP$$coNP$$P^{NP}$ ditutup di bawah pengurangan Karp); apakah itu benar?$NP$

Jadi haruskah gambarnya terlihat seperti sekarang, yaitu, sesuatu seperti yang berikut ini?$P \subset P^{NP} \subset PH \subset PSPACE$

Apakah ada beberapa urutan baru yang memainkan peran yang sesuai dengan hierarki polinomial? Apakah ada urutan alami dari kelas kompleksitas , C 1 = P N P , C 2 = ? , ..., sedemikian rupa sehingga setiap kelas kompleksitas ditutup di bawah pengurangan Turing? Apa "batas" dari urutan ini: apakah itu P H ? Apakah diharapkan setiap kelas dalam urutan berbeda dari yang sebelumnya? (Dengan "diharapkan", maksud saya di bawah dugaan yang masuk akal, mirip dengan pengertian di mana diharapkan bahwa P ≠ N P. )$C_0=P$$C_1=P^{NP}$$C_2=?$$PH$$P \ne NP$

Terkait: Banyak-satu pengurangan vs pengurangan Turing untuk menentukan NPC . Artikel itu menjelaskan bahwa alasan kami bekerja dengan pengurangan Karp adalah karena ia memberi kami hierarki yang lebih halus, lebih kaya, dan lebih tepat. Pada dasarnya, saya bertanya-tanya seperti apa hirarki itu jika kita bekerja dengan pengurangan Turing: seperti apa hirarki yang lebih kasar, kurang kaya, kurang tepat.

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

Jika hierarki polinomial tidak runtuh, semua inklusi adalah ketat.