Apa contoh alami dari bukti yang tidak dapat direlatifikasi?

13

Seperti yang saya pahami, bukti bahwa P = NP atau P ≠ NP harus tidak dapat direlatifikasi (seperti dalam teori rekursi).

Namun, pada dasarnya semua bukti tampaknya relativizable.

Apa contoh yang baik dari bukti yang tidak dapat direlatifikasi, dari jenis yang perlu P = NP / P ≠ NP bukti, yang tidak sepele atau dibuat-buat?

(Saya bukan ahli teori rekursi, jadi mohon maafkan kurangnya kutipan.)

[EDIT: posting mathoverflow lebih baik ]

Sai
sumber
6
Untuk menyalin saran saya dari MO dan mengeluarkannya: contoh kanonik yang saya ketahui adalah bukti IP = PSPACE, di mana khususnya dimasukkannya PSPACE dalam IP dilakukan dengan menunjukkan bukti interaktif untuk PSPACE tertentu Masalah-lengkap, teknik non-relativizable - masalah tertentu tidak relativize.
Steven Stadnicki
5
AIPAPSPACEA
4
@Steven: TBQF relativized dapat dibentuk dengan mengizinkan gerbang oracle, bukan hanya gerbang logika (standar).
3
@RickyDemer Bahkan, inti dari buktinya bekerja dengan menafsirkan rumus sebagai polinomial tingkat rendah, yang tidak dapat dijalankan ketika Anda memiliki (katakanlah) gerbang oracle yang seragam acak.
Yonatan N
1
btw hasil P =? NP pada relativization dikenal sebagai teorema Baker-Gill-Solovay 1975 . buktinya juga dapat ditemukan misalnya di Hopcroft / Ullman . @ richerby / Sai tidak ada alasan untuk bermigrasi setelah kedua pertanyaan dimasukkan, lebih untuk referensi di masa mendatang. juga perhatikan tampaknya tidak ada kebijakan lintas situs penumpukan stackexchange resmi pada crossposting (karenanya beberapa kebingungan dapat dimengerti).
vzn

Jawaban:

24

IP=PSPACEAIPAPSPACEAPSPACEmasalah-lengkap TQBF diberikan dengan mempertimbangkan perluasan formula boolean yang dikuantifikasi ke polinomial derajat rendah di atas bidang yang sesuai. Jika kita diberi formula boolean yang din Relativized (dengan gerbang oracle), ekstensi seperti itu tidak ada.

CDAA~ACADA~CDAA~CA~DA. Aaronson dan Wigderson menunjukkan bahwa algebrize, tetapi banyak hasil lainnya, termasuk , tidak.IP=PSPACENPP

Contoh terbaru dari teknik yang tidak membuat aljabar atau relativize adalah bukti Ryan Williams bahwa . Pemisahan tidak algebrize: ada oracle dan perpanjangan rendah derajat sehingga . Secara intuitif alasan mengapa buktinya menghindari penghalang adalah karena ia bergantung pada keberadaan algoritme kepuasan yang lebih cepat daripada sepele untukNEXPACCAA~NEXPA~ACCAACCsirkuit, dan algoritma menggunakan sifat non-relativizing dan non-algebrizing dari sirkuit tersebut. Ryan mencatat dalam makalah bahwa semua algoritma kepuasan yang diketahui lebih cepat dari sepele rusak ketika oracle atau ekstensi aljabar dari oracle ditambahkan.

Ada juga pendekatan yang menarik untuk memahami relativisasi melalui logika. Dalam sebuah manuskrip tua, Arora, Impagliazzo, dan Vazirani mendefinisikan sistem aksioma sedemikian rupa sehingga hasil relativizing adalah persis yang mengikuti dari aksioma, sementara hasil non-relativizing independen dari sistem. Sebuah makalah oleh Impagliazzo, Kabanets, dan Kolokolova melakukan hal serupa untuk algebrization dengan memperkenalkan aksioma tambahan untuk yang didefinisikan oleh Arora, Impagliazzo dan Vazirani. Mereka menunjukkan bahwa hasil non-relativizing paling dikenal mengikuti dari aksioma mereka, sementara P vs NP, antara lain, tidak tergantung pada mereka.

Maaf jika ada yang salah, saya bukan ahli.

Sasho Nikolov
sumber
7
Ada contoh lain tentang bukti non-relativizing dalam makalah Aaronson-Wigderson, seperti , , , dll.NEXPMIPMAEXPP/polyPromiseMASIZE(nk)
Robin Kothari
10

Berikut adalah daftar bukti yang tidak dapat direlatifikasi:

  1. Teorema PCP

  2. Komitmen bergantung pada instans menyiratkan protokol pengetahuan nol:
    Kesetaraan antara Pengetahuan nol dan Komitmen

  3. Tidak ada obfuscator sirkuit "kotak hitam virtual" yang efisien untuk sirkuit umum:
    Kesetaraan antara Pengetahuan dan Komitmen Nol

  4. PSPACE dapat direduksi menjadi evaluasi produk ringkas : PSPACe selamat dari kemacetan tiga-bitS5

  5. Terhadap prover yang tidak terentang, NEXP memiliki sistem 2-prover proof interaktif minimal-minimal: sistem proof
    satu putaran dua-prover: kekuatan dan masalah mereka

  6. Terhadap prover yang kemungkinan terjerat, NEXP memiliki protokol MIP yang lebih interaktif:
    Bukti interaktif multi-prover untuk suara NEXP terhadap prover yang terjerat

  7. NP memiliki bukti-bukti pengetahuan NISZK yang efisien-terbukti dengan ekstraksi pengetahuan yang sempurna dalam model bit tersembunyi "distribusi sampel non-standar yang efisien," dan bukti-pengetahuan NIPZK yang membuktikan efisiensi-pengetahuan dalam model bit tersembunyi (nyata). Lebih jauh, jika sampler diperbolehkan memiliki kemungkinan kecil untuk menghasilkan (dan kesehatan hanya diperlukan untuk menahan ketika sampler tidak menghasilkan ), maka "NISZK" dari kalimat sebelumnya dapat diganti dengan "NIPZK" . Jonathan Katz, Topik Tingkat Lanjut dalam Kriptografi, Kuliah 13

    Catatan: Ekstraksi pengetahuan sempurna diikuti dengan inspeksi bagian kesehatan pada halaman 2. Ekstraksi pengetahuan (tidak sempurna) berlaku untuk alasan yang sama seperti kesehatan tidak sempurna, seperti dijelaskan di bagian atas halaman 5. Pengetahuan nol sempurna dapat diperoleh dengan meminta simulator menggunakan matriks Hamiltonian sebagai permutasi , dan beberapa string-bit aktual yang berhubungan dengan bit-bias dengan nilai 0 sebagai diri mereka sendiri, hanya sebagian besar di lokasi yang berbeda. Kalimat "selanjutnya" diikuti dengan memiliki sampler outputCiπ jika tidak dapat memilih elemen dari {0,1,2,3, ..., n! -1} sempurna seragam dalam waktu yang cukup kecil, karena pilihan seperti itu akan memungkinkan untuk generasi seragam yang sempurna dari suatu matriks grafik siklus terarah atau permutasi dari simpul.

Kaveh
sumber
7

ini adalah survei lapangan yang bagus oleh seorang ahli terkemuka yang merangkum / merinci beberapa poin dari jawaban lain sejauh ini & memiliki contoh tambahan.

[1] Peran Relativization dalam Teori Kompleksitas Fortnow

Beberapa hasil nonrelativizing baru-baru ini di bidang bukti interaktif telah menyebabkan banyak orang meninjau kembali pentingnya relativization. Dalam makalah ini kita akan melihat bagaimana kompleksitas teori digunakan dan menyalahgunakan hasil ramalan. Kami memberikan perhatian khusus pada sistem bukti interaktif baru dan hasil pengecekan program dan mencoba memahami mengapa mereka tidak mengalami relativisasi. Kami memberikan beberapa hasil baru yang dapat membantu kami memahami pertanyaan-pertanyaan ini dengan lebih baik.

vzn
sumber
6
+1 ini adalah survei yang bagus, tetapi harus disebutkan bahwa survei ini mencakup
Sasho Nikolov
benar; akan sangat membantu jika penulis memasukkan tanggal dalam makalah mereka lebih banyak ... survei yang lebih baru juga akan membantu, topik tersebut tampaknya jarang disurvei. daerah ini tampaknya tidak banyak berubah & tidak begitu jelas berapa banyak hasil baru yang muncul sejak tanggal tersebut.
vzn
3
untuk hasil baru: Saya pikir beberapa hasil oracle baru telah muncul sejak itu berkaitan dengan kelas kompleksitas kuantum. lebih penting lagi, telah ada perkembangan dalam hal apa arti hasil oracle: penghalang algebrization dan non-algebrizing bukti Ryan dari jawaban saya, makalah terkait cs.sfu.ca/ ~ kabanets/papers/act-full.pdf , dan mungkin Karya Boaz Barak tentang pengurangan kotak hitam di crypto.
Sasho Nikolov