Intuisi di balik Relativization

10

Saya mengambil kursus tentang Kompleksitas Komputasi. Masalah saya adalah saya tidak mengerti metode Relativization . Saya mencoba menemukan sedikit intuisi di banyak buku teks, sayangnya, sejauh ini tidak berhasil. Saya akan menghargai jika seseorang dapat menjelaskan topik ini sehingga saya akan dapat melanjutkan sendiri. Beberapa kalimat berikut adalah pertanyaan dan pemikiran saya tentang relativisasi, mereka akan membantu menavigasi diskusi.

Sangat sering relativization datang dibandingkan dengan diagonalisasi, yang merupakan metode yang membantu membedakan antara himpunan yang dapat dihitung dan yang tidak terhitung. Entah bagaimana berasal dari relativization bahwa pertanyaan versus tidak dapat diselesaikan dengan diagonalisasi. Saya tidak benar-benar melihat gagasan mengapa relativisasi menunjukkan tidak adanya diagonalisasi, dan jika tidak ada gunanya, mengapa sebenarnya tidak berguna.N PPNP

Ide di balik mesin Turing oracle pada awalnya sangat jelas. Namun, ketika menyangkut dan intuisi menghilang. Oracle adalah kotak hitam yang dirancang untuk bahasa khusus dan menjawab pertanyaan apakah string pada input oracle dalam bahasa dalam waktu 1. Seperti yang saya mengerti TM yang berisi oracle hanya membuat beberapa operasi tambahan dan meminta oracle. Jadi inti dari TM adalah oracle, yang lainnya kurang penting. Apa perbedaan antara dan , bahkan ramalan keduanya bekerja dalam waktu 1. N P A P A P A N P AMANPSEBUAHPSEBUAHPSEBUAHNPSEBUAH

Hal terakhir adalah membuktikan adanya sebuah ramalan sehingga . Saya menemukan buktinya di beberapa buku teks dan di semua buktinya tampaknya sangat kabur. Saya mencoba menggunakan "Pengantar kompleksitas" oleh Sipser, Bab9. Ketidaksarikan , dan tidak mendapatkan ide konstruksi daftar semua waktu polynomial oracle .P BN P BBPBNPBM.saya

Ini kurang lebih semua yang saya tahu tentang relativization, saya akan menghargai jika seseorang akan memutuskan untuk membagikan pemikirannya tentang topik tersebut.

Tambahan : di salah satu buku teks saya menemukan contoh bahasa (Kompleksitas Komputasi: Suatu Pendekatan Modern oleh Boaz Barak Sanjeev Arora. Teorema 3.7. Halaman 74). itu adalah bahasa unary. Saya percaya bahwa (1,11,111,1111, ...) semuanya ada di . Penulis menegaskan bahwa bahasa seperti itu ada dalam yang mana saya tidak bisa mengerti mengapa, maka ramalan untuk B dapat menyelesaikan semuanya dalam waktu 1. Mengapa kita perlu TM non-deterministik dengan oracle. Jika tidak contoh yang baik dari silakan memasukkan Anda sehingga untuk menyetujui keberadaan .U B = { 1 n : s o m e s t r i n g o f l e n g t h n i s i n B } U B N P B N P B N P BNPBUB={1n:sHaime strsayang Haif length n sayas sayan B}UBNPBNPBNPB

com
sumber
2
dan N P A adalah kelas bahasa, mereka bukan mesin Turing. Anda mengatakan bahwa oracle adalah "inti" dari TM, tetapi itu belum tentu benar. Misalnya, bagaimana jika A adalah bahasa kosong? PSEBUAHNPSEBUAHSEBUAH
Yuval Filmus
ini adalah topik yang sangat sulit pada umumnya tidak terlalu banyak untuk mahasiswa. satu aspek adalah bahwa nubuat agak tergantung pada model. yaitu tidak ada cara yang konsisten untuk merancang oracle. intuisi dasarnya adalah bahwa ini adalah mesin dengan kemampuan subrutin "ajaib" (diberikan oleh oracle) sedemikian rupa sehingga mesin + oracle selalu setidaknya sekuat mesin asli, tetapi terkadang tidak jauh lebih kuat ...
vzn
1
pertanyaan terkait: cs.stackexchange.com/questions/1271/… , dengan jawaban yang bagus dari Tsuyoshi Ito
A.Schulz
Saya tidak yakin apa yang Anda minta. Anda tampaknya bingung tentang bukti BGS dan juga mengajukan banyak pertanyaan lain. Silakan ajukan satu pertanyaan terfokus. Perhatikan bahwa ini bukan forum atau forum diskusi, ini adalah situs tanya jawab.
Kaveh
Apakah Anda meminta penjelasan tentang bukti BGS untuk keberadaan oracle yang memisahkan P dan NP? Apakah Anda meminta penjelasan tentang hubungan relativiasi dan diagonalisasi? (jika demikian, apakah jawaban Tsuyoshi dalam pertanyaan berbaris menjawab pertanyaan Anda? jika tidak tolong jelaskan mengapa tidak.)
Kaveh

Jawaban:

7

PSEBUAHNPSEBUAHSEBUAHNPSEBUAHSEBUAHSEBUAHPSEBUAH

Pål GD
sumber
1
Terima kasih banyak atas jawabannya, dapatkah Anda memberi contoh bagaimana kekuatan NTM dengan oracle membantu kami mengenali lebih banyak bahasa daripada DTM dengan oracle. Bukti BGS menunjukkan bahasa seperti itu tetapi saya tidak mendapatkan buktinya.
com
SEBUAHPNPAA
PNPP