Mekanisme akses oracle Ruzzo-Simon-Tompa

Dalam sebuah makalah tentang merelatifkan perhitungan logspace, Ladner dan Lynch membangun sebuah oracle relatif terhadap yang . Ada beberapa contoh yang lebih patologis dalam hal ini dalam literatur. Saya telah membaca beberapa makalah tentang kelas ruang kecil yang direlatifikasi, dan salah satu alat utama di bidang ini adalah mekanisme akses oracle Ruzzo-Simon-Tompa (RST) yang menuntut agar mesin turing yang dibatasi ruang yang tidak deterministik bertindak secara deterministik sambil membuat pertanyaan ke oracle. $\mathsf{NL} \nsubseteq \mathsf{P}$

Sekarang perhatikan keluarga sirkuit dengan gerbang oracle - katakanlah, , di mana adalah kelas kompleksitas rangkaian yang mengandung logspace akses oracle ke kelas lain , melalui gerbang oracle ditambahkan ke dasar . Apakah ada contoh patologis yang serupa dalam semangat dengan kertas Ladner-Lynch, yang dikenal untuk kelas-kelas seperti itu? Apa yang akan menjadi batasan RST yang diperlukan untuk kelas seperti itu? Jika memang ada contoh-contoh seperti itu, apakah saya benar dalam menebak bahwa analog RST akan bersikeras bahwa menjadi rangkaian keluarga logspace-uniform? $A^B$ $A$ $B$ $A$ $A$

cc.complexity-theory complexity-classes circuit-complexity oracles relativization Nikhil
sumber

Jawaban:

$AC^k$ $NC^k$

Klaus Aehlig, Stephen Cook dan Phuong Nguyen: Merelatifkan Kelas Kompleksitas Kecil dan Teori mereka, CSL 2007, Springer LNCS 4646

Jan Johannsen
sumber

Terima kasih untuk penunjuknya. Tapi saya masih belum punya ide yang jelas tentang bagaimana RST berlaku untuk sirkuit dengan gerbang oracle. Saya harap Anda tidak keberatan jika saya menunggu sebentar untuk melihat apakah ada hal lain yang menarik dalam masalah ini, sebelum menerima jawaban Anda.

Nikhil