Kelas kompleksitas di mana

Salah satu motivasi yang mungkin untuk mempelajari kelas kompleksitas komputasi adalah untuk memahami kekuatan berbagai jenis sumber daya komputasi (keacakan, non-determinisme, efek kuantum, dll.). Jika kita melihatnya dari perspektif ini, maka sepertinya kita dapat memperoleh satu aksioma yang masuk akal untuk setiap upaya mengkarakterisasi perhitungan mana yang layak dalam beberapa model:

• Setiap perhitungan yang layak selalu dapat meminta perhitungan lain yang layak sebagai subrutin. Dengan kata lain, anggaplah program dianggap layak untuk dijalankan. Kemudian jika kita membuat program baru dengan menghubungkan P dan Q ke atas, sehingga P membuat panggilan subrutin ke Q , maka program baru ini juga layak.$P,Q$$P$$Q$$P$$Q$

Diterjemahkan ke dalam bahasa kelas kompleksitas, aksioma ini sama dengan persyaratan berikut:

• Jika adalah kelas kompleksitas dimaksudkan untuk menangkap yang perhitungan yang layak dalam beberapa model, lalu kita harus memiliki C C = C .$C$$C^C = C$

(Berikut merupakan perhitungan di C yang dapat memanggil sebuah oracle dari C ;. Itu kelas kompleksitas oracle) Jadi, mari kita sebut kelas kompleksitas C masuk akal jika memenuhi C C = C .$C^C$$C$$C$$C$ $C^C=C$

Pertanyaan saya: Kelas kompleksitas apa yang kita ketahui, yang masuk akal (menurut definisi ini masuk akal)?

Misalnya, adalah masuk akal, karena P P = P . Apakah kita memiliki B P P B P P = B P P ? Bagaimana dengan B Q P B Q P = B Q P ? Apa saja kelas kompleksitas lain yang memenuhi kriteria ini?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Saya menduga bahwa (atau setidaknya, itu akan menjadi tebakan terbaik kami, bahkan jika kami tidak dapat membuktikannya). Apakah ada kelas kompleksitas yang menangkap perhitungan non-deterministik dan yang masuk akal, di bawah definisi ini? Jika kita membiarkan C menunjukkan kelas kompleksitas terkecil sehingga N P ⊆ C dan C C ⊆ C , adakah karakterisasi bersih dari C ini ?$NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

telah dibuktikan dalamStrengths and Weaknesses of Quantum ComputingBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

Menurut kompleksitas kebun binatang, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Berikut adalah beberapa jawaban untuk beberapa pertanyaan, tetapi tentu saja tidak semuanya:

Rupanya, menurut Wikipedia , kita memiliki , B P P B P P = B P P , P S P A C E P S P A C E = P S P A C E , L L = L , dan ⊕ P ⊕ $P^P=P$$BPP^{BPP}=BPP$$PSPACE^{PSPACE}=PSPACE$$L^L=L$ . Lihat jugaApa itu kelas kompleksitas ⊕ P$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$ , yang mengamati bahwa.$\oplus P^{\oplus P} = \oplus P$

Juga, jika , maka C ditutup di bawah komplemen. Jadi tidak mungkin bahwa N P N P = N P : ini akan menyiratkan bahwa N P = co- N P , yang tampaknya tidak mungkin. Sepertinya kelas kompleksitas masuk akal terkecil yang berisi N $C^C=C$$C$$NP^{NP}=NP$$NP=\textit{co-}NP$$NP$ adalah (lihat Wikipedia ).$PH$

Saya tidak tahu apa situasinya . Saya tidak tahu apakah ada contoh menarik lainnya dari kelas kompleksitas yang masuk akal.$BQP$

Sebuah kelas kompleksitas disebut self-rendah tepatnya ketika C C = C . Secara umum, "lowness" banyak dipelajari di tahun 80-an dan 90-an - google akan mengungkap banyak hal untuk Anda.$C$$C^C = C$

Komentar ini mencantumkan L (logspace), NC (kedalaman polylog), P, BPP, BQP, dan PSPACE sebagai contoh kelas kompleksitas rendah diri.