Apakah ada referensi yang pasti untuk mesin Turing dengan beberapa kaset oracle?

10

Sebagian besar literatur tampaknya berkaitan dengan mesin dengan nubuat tunggal untuk masalah tertentu, namun tampaknya ada beberapa makalah yang menganggap mesin dengan banyak nubuat. Apakah ada makalah atau tesis yang bagus yang memberikan gambaran umum tentang apa yang diketahui tentang mesin seperti itu? Secara khusus saya tertarik pada P dengan banyak nubuat.

oracles turing-machines Joe Fitzsimons
sumber
3
Jika Anda hanya ingin sejumlah N dari oracle, Anda bisa mendefinisikan oracle senyawa N-in-1 dengan menggunakan bit log (N) log pertama dari oracle untuk menunjukkan suboracle mana yang ingin Anda query. Apakah saya melewatkan sesuatu?
Niel de Beaudrap
Ya, saya sudah memikirkan itu. Namun, saya tertarik pada set oracle tertentu, dan karenanya lebih alami untuk menganggapnya secara terpisah daripada sebagai objek majemuk. Saya pikir mungkin ada beberapa hasil yang bagus dalam arah ini.
Joe Fitzsimons
1
hanya untuk rasa ingin tahu, apakah memiliki beberapa ramalan menambah lebih banyak daya komputasi sehubungan dengan satu mesin ramalan? Sepertinya saya tidak, karena Anda hanya mengambil oracle yang sesuai dengan bahasa di kelas kompleksitas tertinggi. Juga, memiliki jumlah oracle yang tetap akan memperlambat mesin dengan konstan.
Marcos Villagra
1
Saya dengan komentar Marcos tentang oracle terkuat yang merangkul yang lain .. tapi saya tertarik dengan apa yang ada dalam pikiran Anda sekarang!
Daniel Apon
1
Apakah Anda berpikir untuk memperbolehkan banyak oracle, di mana TM diizinkan untuk memilih oracle yang akan ditanyakan? Dengan pengaturan seperti itu mungkin ada perbedaan yang menarik antara satu set oracle di mana masing-masing secara ketat lebih lemah daripada beberapa oracle Q lainnya, dan Q itu sendiri.
András Salamon

Jawaban:

5

Berikut ini adalah makalah yang lebih baru memberikan perbedaan antara nubuat tunggal vs banyak dimotivasi oleh kriptografi:

Donald Beaver dan Joan Feigenbaum. Menyembunyikan instance dalam permintaan multioracle . STACS 1990. Catatan Ceramah Springer dalam Ilmu Komputer, 1990, Volume 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
sumber
hanya sebuah pertanyaan, saya menganggap bahwa konsep multi-oracle hanya masuk akal jika oracle tidak dapat runtuh satu sama lain karena beberapa alasan keamanan (dianggap?)?
Ahmed Masud
3

Berikut ini adalah makalah yang lebih tua yang mungkin berguna: Mesin Logspace dengan Beberapa Oracle Tapes oleh Nancy Lynch di MIT ( PDF ) Teorema 2.2 tertentu, pada PDF-halaman 5, mungkin merupakan jenis hal yang Anda cari. Ada juga bagian tentang hierarki yang ditentukan oleh jumlah kaset oracle yang berbeda per mesin.

Penafian setelah fakta: Sepertinya pertanyaan serupa dan (bahkan lebih mirip) jawaban diberikan di sini .

Daniel Apon
sumber