Sirkuit dengan oracle vs. Mesin Turing dengan oracle

13

Sederhananya: apa korespondensi antara mesin Turing dengan oracle, dan keluarga sirkuit seragam dengan oracle? Bagaimana yang terakhir didefinisikan untuk mendapatkan model komputasi yang sama, untuk mesin Turing oracle yang diberikan?

Ini mungkin pertanyaan mendasar, tetapi tidak jelas ke mana harus mencari, dan saya adalah tipe orang yang suka memastikan bahwa yayasan saya menggunakan mortar berkualitas baik. Jika ada referensi standar, harap tunjuk saya ke sana. (Buku Papadimitriou, misalnya, tampaknya tidak menggambarkan sirkuit dengan oracle sama sekali.)

Hipotesis kerja saya adalah ini: rangkaian keluarga yang seragam dengan akses ke oracle (misalnya untuk menyelesaikan masalah NP-complete) didefinisikan sebagai berikut:

  • Satu mendefinisikan keluarga tak terbatas dari "gerbang oracle" O n  , satu untuk setiap ukuran sirkuit n, masing-masing yang menghitung fungsi f n  : {0,1} cn  → {0,1} untuk beberapa konstanta c.

  • Fungsi f n yang dihitung oleh gerbang oracle O n harus "seragam" dalam arti berikut: untuk setiap n <N dan x  ∈ {0,1} n , kita memerlukan f n ( x ) = f N (0 c ( N − n)  x  ) --- yaitu, gerbang oracle harus menggunakan "penyandian" yang konsisten dan extensbile dari input mereka.

  • Satu kemudian mendefinisikan rangkaian keluarga seragam, di mana gerbang oracle adalah di antara operasi yang diizinkan ke sirkuit, membatasi sirkuit untuk ukuran input n untuk menggunakan gerbang O n .

Saya membayangkan bahwa beberapa pilihan di atas dapat diperbaiki secara sewenang-wenang tanpa kehilangan sifat umum apa pun. Yang saya minati adalah referensi untuk korespondensi, atau setidaknya deskripsi tentang bagaimana memodifikasi deskripsi di atas untuk mendapatkan yang standar.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
sumber
Karena saya tahu Anda bekerja dalam informasi kuantum, saya akan merekomendasikan survei John Watrous tentang kompleksitas komputasi Quantum, di mana ia juga berbicara tentang oracle di sirkuit kuantum dan menanyakan oracle dalam superposisi.
Robin Kothari
Artikel Watrous juga merupakan referensi yang bagus. Tapi apa yang ternyata saya butuhkan dalam kasus ini adalah entah bagaimana tidak puas dengan gagasan bahwa ada orang yang ingin mendefinisikan keluarga sirkuit relativized dengan cara yang tidak sesuai dengan hanya menguji predikat yang sama untuk panjang string terbatas yang berbeda, dengan menjadi mengingatkan bahwa semantik oracle klasik adalah untuk mengindikasikan keanggotaan dalam beberapa set. Ternyata, gambar gerbang sirkuit dengan simbol "∈A?" pada mereka semua yang saya butuhkan.
Niel de Beaudrap

Jawaban:

19

Referensi terbaik untuk sirkuit relativized adalah kertas Chris Wilson "Relativized NC" http://www.springerlink.com/content/u727654246wu8662/

Kondisi kedua yang Anda miliki (penutupan ke bawah O_n) tidak diperlukan untuk mendapatkan kesetaraan antara P ^ O dan sirkuit ukuran-poli yang seragam dengan oracle O. Juga kondisi ketiga Anda harus dibuang, ukuran sirkuit akan mencegah akses ke O_m untuk m lebih besar dari ukuran sirkuit.

Lance Fortnow
sumber
Tidak ada komentar eksplisit dalam makalah Wilson di gerbang oracle itu sendiri; tetapi jika dipikir-pikir jika Anda menganggap serius oracle sebagai mewakili keanggotaan dalam serangkaian string boolean seperti dengan TM, maka kondisi kedua saya hanyalah masalah (yaitu tidak perlu dikatakan). Dengan pengamatan Anda tentang kelebihan kondisi ketiga saya, maka sudah cukup untuk memiliki keluarga gerbang tanpa batas yang memutuskan keanggotaan dalam A untuk ukuran string terbatas apa pun. Itu bekerja untuk saya; Saya berharap saya telah memikirkannya lebih awal.
Niel de Beaudrap
3
Keterangan untuk kepentingan penonton biasa --- Artikel Wilson mendefinisikan kontribusi kedalaman gerbang oracle pada k bits menjadi ceil (log k), dalam analogi yang jelas dengan karya sebelumnya oleh Cook ("Taksonomi masalah dengan algoritma paralel cepat" , Inform. And Control, 64). Ada masalah teknis apakah mengizinkan pertanyaan oracle dalam proses membangun sirkuit itu sendiri (masing-masing mungkin juga menggunakan oracle): ia berkomentar bahwa itu tampaknya tidak masalah. Pada akhirnya, ia tidak puas dengan keberadaan A yang NC_1 ^ A tidak terkandung dalam NSPACE ^ A (O (n ^ k)), untuk konstanta k apa pun.
Niel de Beaudrap