Apakah Oracles Asosiatif?

Pertanyaan ini mungkin memiliki jawaban yang jelas ... tetapi inilah pertanyaannya. Secara intuitif, ini adalah pernyataan masuk akal berikut - "mesin dengan subrutin A yang pada gilirannya memiliki subrutin B sama dengan mesin dengan subrutin A yang memiliki akses ke subrutin B".

Untuk mendefinisikan masalah ini secara formal, saya akan menggunakan beberapa notasi yang tidak konvensional. Ketika saya mengatakan $A^B$ , saya memberikan $A$ oracle untuk masalah $B-Complete$ . misalnya $NP^{NP}=NP^{SAT}=\Sigma_2$ . Dengan notasi "baru" ini, dimungkinkan untuk mendefinisikan $A^{B^C}$ , dan seterusnya. Pertanyaan saya adalah, apakah

• apakah ini cara berpikir yang valid tentang nubuat?
• adalah $(A^B)^C = A^{(B^C)}$

Misalnya, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

Saya tidak bisa memikirkan contoh tandingan yang jelas untuk aturan ini. Siapa saja?

Seperti yang dikatakan Venkat dalam komentar, tampaknya sulit untuk memahami definisi Anda untuk oracle yang tidak didefinisikan sebagai beberapa karakterisasi mesin.

Misalkan adalah himpunan TM dalam A dengan oracle yang merupakan mesin dalam ( B dengan oracle dalam mesin dalam C ). Jelas bahwa mesin di A dapat memanggil C : ia hanya memanggil mesin di B dan memintanya untuk membawa pesan langsung ke $A^{(B^C)}$$A$$B$$C$$A$$C$$B$$C$ .

Saya kira akan menjadi mesin di A yang dapat memanggil oracle di C atau oracle yang (mesin di B yang dapat memanggil mesin di C ) jadi definisi yang persis sama.${(A^B)}^C$$A$$C$$B$$C$

Akhirnya, Anda mungkin menginginkan , yang tentu saja berbeda dari dua lainnya (ambil saja B = C = N P dan A = P , lalu A B , C = N P ∪ c o N P sedangkan A ( B C ) = Σ P 2 ∪ Π p 2 .$A^{B,C}$$B=C=NP$$A=P$$A^{B,C}=NP\cup coNP$$A^{(B^C)}=\Sigma_2^P\cup\Pi_2^p$

Saya akan menulis yang berikut sebagai komentar, tapi terlalu panjang untuk masuk.

Pertama mari kita gambarkan arti dari “algoritma di kelas dengan oracle untuk bahasa A.” (Kebutuhan untuk ini ditunjukkan oleh Tsuyoshi Ito). Kami akan menggunakan konvensi yang sama yang digunakan oleh Ladner dan Lynch . Konvensi ini dijelaskan dengan baik oleh Bennett & Gill :$\bf C$

dapat didefinisikan dengan berbagai cara, tergantung pada bagaimana rekaman kueri ditangani. Kami mengikuti konvensi Ladner dan Lynch [LL]: Tape kueri tidak dibebankan terhadap batas ruang, tetapi untuk menjaga agar tidak digunakan sebagai pita kerja, pita kueri adalah satu arah dan hanya menulis, dan dihapus secara otomatis mengikuti setiap permintaan. (Simon [Si] memperlakukan pita kueri sebagai salah satu dari pita kerja, pita baca / tulis dua arah yang dibebankan terhadap batas ruang. Definisi Ladner-Lynch kurang ketat dan mungkin lebih alami, karena untuk ramalan acakA∈ L O G S P A C E$\bf{LOGSPACE}^A$$A \in \bf{LOGSPACE}^A$ berlaku dengan probabilitas 1 untuk [LL] tetapi tidak untuk [Si])

[LL] RE LADNER DAN NA LYNCH, Relatisasi pertanyaan tentang kompabilitas ruang log , Matematika. Teori Sistem, 10 (1976), hlm. 19-32.

[Si] J. SIMON, Pada Beberapa Masalah Sentral dalam Kompleksitas Komputasi , Tek. Rep TR 75-224, Departemen Ilmu Komputer, Universitas Cornell, Ithaca, NY, 1975.

Definisi standar kelas kompleksitas mesin oracle adalah sebagai berikut: Biarkan B dan C menjadi kelas kompleksitas . Kemudian, adalah kelas kompleksitas yang sah, yang didefinisikan sebagai X = ⋃ L ∈ C B L . Di sini, B $X = B^C$$X = \bigcup_{L\in C}{B^L}$$B^L$ mewakili kelas kompleksitas masalah keputusan dipecahkan oleh algoritma di kelas B dengan oracle untuk bahasa L.

Karena X adalah kelas kompleksitas yang sah, untuk setiap kelas kompleksitas A, kita dapat berbicara tentang kelas kompleksitas dan X A = ( B C ) $A^X = A^{(B^C)}$$X^A = (B^C)^A$ .

• mengacu pada kelas kompleksitas masalah keputusan dipecahkan oleh algoritma di kelas A dengan oracle untuk setiap bahasa L ' ∈ X = ⋃ L ∈ C B L . Dengan kata lain, A X = ⋃ L ′ ∈ { ⋃ L ∈ C B L } A L ′ .$A^X$$L' \in X = \bigcup_{L\in C}{B^L}$$A ^ X = \bigcup\limits_{L'\in \{\bigcup\limits_{L\in C}{B^L}\}}{A^{L'}}$

• mengacu pada kelas kompleksitas masalah keputusan dipecahkan oleh algoritma di kelas X = ⋃ L ∈ C B L dengan oracle untuk setiap bahasa L ' ∈ A . Dengan kata lain, X A = ⋃ L ′ ∈ A X L ′ = ⋃ L ′ ∈ A ( ⋃ L ∈ C B L ) L ′ .$X^A$$X = \bigcup_{L\in C}{B^L}$$L' \in A$$X ^ A = \bigcup_{L' \in A} {{X^{L'}}} = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}}$

Klaim: $(B^{L_1})^{L'} \cup (B^{L_2})^{L'} = (B^{L'})^{L_1 \cup L_2}$ .

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

Oleh karena itu, seseorang dapat menulis $X ^ A = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}} = \bigcup_{L \in C, L' \in A} {{{\left( B^{L'} \right)}^L}}$ .

Contoh

$\bf X = \bf{P^{NP}}$$\bf{coNP} \subseteq \bf X$$\bf {NP}$$\bf{coNP^{NP}} \subseteq \bf{X^{NP}} = (\bf{P^{NP}})^{\bf{NP}}$

Epilog

Sebuah diskusi yang bermanfaat dengan Tsuyoshi Ito mengungkapkan (bagi saya) bahwa tidak mudah untuk secara ganda merelatifkan kelas kompleksitas. Bahkan, mendefinisikan satu pun tampaknya bermasalah. Saya harus belajar lebih banyak untuk melihat apakah ada definisi yang memuaskan yang pernah diberikan. Sementara itu, saya menghargai setiap komentar yang dapat digunakan untuk menyelesaikan masalah ini.