Kekerasan fungsi Boolean yang bising

13

Biarkan f menjadi fungsi Boolean dari variabel Boolean. Misalkan menjadi nilai yang diharapkan dari ketika diperoleh dari dengan membalik setiap koordinat dengan probabilitas .g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2ng(x)=Tϵ(f)(x)f(y)yxϵ/2

Saya tertarik pada kasus di mana secara komputasi sulit untuk memperkirakan . Biarkan saya memperbaiki gagasan "aproksimasi" (tetapi mungkin ada yang lain): Fungsi Boolean mendekati jika saat dan saat . Argumen penghitungan (berdasarkan pada keberadaan kode koreksi kesalahan laju positif) tampaknya memberikan bahwa ada fungsi Boolean yang setiap pendekatannya memerlukan sirkuit ukuran eksponensial. Tetapi pertanyaannya adalah apa yang terjadi ketika untuk memulai dengan NP atau di lingkungannya.h g h ( x ) = 1 g ( x ) 0,9 h ( x ) = 0 g ( x ) 0,1 fghgh(x)=1g(x)0.9h(x)=0g(x)0.1f

T1: Apakah ada contoh dijelaskan oleh sirkuit NP (atau P-space) sehingga setiap adalah NP keras, atau keras dalam arti yang lebih lemah.hfh

Untuk melihat bahwa mungkin tidak selalu mudah (saya berterima kasih kepada Johan Hastad untuk diskusi yang bermanfaat tentang hal itu) kita dapat mempertimbangkan properti grafik memiliki klik ukuran , untuk input acak, dapat dibayangkan bahwa sulit untuk mendeteksi jika ada klik besar tetapi ini dimanifestasikan dengan memiliki lebih dari yang diharapkan klik ukuran n pada grafik berisik. Dalam hal ini setiap akan cenderung-sulit (tetapi tidak dapat dibuktikan, dan tidak terlalu keras seperti yang dikatakan oleh sirkuit kuasi-polinomial).n 1 / 4 hhn1/4h

T2: Bagaimana situasinya jika mulai dengan adalah kompleksitas yang rendah. ( , monoton , , dll.)fAC0TC0ACC

T3: Bagaimana situasi untuk beberapa contoh dasar fungsi Boolean. (Pertanyaannya dapat diperluas juga ke fungsi bernilai nyata.)

Q4: Dapatkah pertanyaan di atas ditanyakan secara formal untuk model komputasi (mesin Turing) yang seragam?

Pembaruan: Mengingat jawaban Andy (Hai, Andy), saya pikir pertanyaan paling menarik adalah memahami situasi untuk berbagai fungsi tertentu.

Perbarui pertanyaan lain Q5 [Q1 untuk fungsi monoton] (juga mengingat jawaban Andy). Bagaimana situasi jika adalah monoton? Bisakah kita masih menyandikan NP dengan lengkap pertanyaan>f

Gil Kalai
sumber
saya pertanyaan ini tentang aproksimasi sirkuit terkait. pertanyaan Anda tampaknya mirip dengan pertanyaan P / poly vs NP.
vzn

Jawaban:

14

untuk Pertanyaan 1, jawabannya adalah Ya, dan dapat ditunjukkan sebagai berikut. (Saya juga secara implisit akan membuat sketsa jawaban afirmatif untuk Q4, karena argumennya seragam dan akan memperlakukan semua panjang input sekaligus.)

Perbaiki setiap bahasa NP-lengkap , dan keluarga kode koreksi kesalahan biner yang baik (dengan tingkat 1/4 dan mengoreksi dari fraksi .1 kesalahan, katakanlah). Biarkan E n c n : { 0 , 1 } n{ 0 , 1 } 4 n menjadi fungsi penyandian untuk panjang n ; kami menggunakan beberapa kode di mana E n c = { E n c n } dapat dihitung dengan algoritma polinomial-waktu yang seragam.LEncn:{0,1}n{0,1}4nnEnc={Encn}

Tentukan sebagai himpunan string z yang paling jauh jaraknya .05 | z | dari codeword y E n c ( L ) encoding beberapa unsur L . Perhatikan bahwa L ' di NP, karena Anda bisa menebak dan memeriksa codeword dekatnya, kata diterjemahkan, dan sertifikat NP untuk keanggotaan kata diterjemahkan dalam L . Lz.05|z|yEnc(L)LLL

Maka klaimnya adalah bahwa setiap "perkiraan" dalam pengertian Anda adalah NP-hard untuk ε = .01 . Karena jika kita mempertimbangkan kata sandi yang valid y = E n c ( x ) dengan panjang 4 n , maka dengan probabilitas 1 - o ( 1 ) di atas versi ε -perturbed acak y dari y , itu akan tidak setuju dengan y paling banyak a 0,05 fraksi koordinat, dan karena itu akan tidak setuju dengan codeword lainnya dari E n cLε=.01y=Enc(x)4n1o(1)εyyy dalamfraksilebih dari 0,05 koordinat. Untuk seperti y ' kita memiliki y 'L ' jika dan hanya jika x L . Jadi jika h adalah setiap pendekatan ke ε versi -smoothed dari L ' dalam arti Anda, maka kita harus memiliki h ( y ) = L ( x ) . Seperti E n c adalah efisien dihitung, ini memberi kita cara untuk secara efisien mengurangi pertanyaan keanggotaan untuk L untuk orang-orang untuk h . BegituEncn.05yyLxLhεLh(y)=L(x)EncLh adalah NP-hard.h

Dua catatan:

(1) pengkodean koreksi kesalahan pada instance NP telah digunakan sebelumnya dalam beberapa makalah, terutama
D. Sivakumar: Tentang Keanggotaan Set Sebanding. J. Comput. Syst. Sci. 59 (2): 270-280 (1999).

(2) argumen di atas tentu saja tidak mengatakan apa pun tentang kompleksitas kasus rata-rata dari setiap masalah NP, karena koreksi kesalahan sedang diterapkan atas dasar instance-by-instance.

Andy Drucker
sumber
8
Perangkat lunak tidak akan membiarkan saya memulai jawaban saya dengan "Hai Gil," dan saya sedikit takut dengan manajemen mikro tingkat ini.
Andy Drucker
2
Ini karena jawaban Anda tidak boleh dimulai dengan "Hai Gil". Ini bukan e-mail pribadi, ini adalah posting di situs web publik. Tentu saja, orang-orang seperti Anda bukan yang ditargetkan oleh ini; itu adalah pengguna yang agak baru yang tidak menyadari konvensi ini yang bertujuan untuk dikendalikan oleh perangkat lunak.
Yuval Filmus
1
Pandangan saya adalah bahwa tidak apa-apa untuk mengakui ketika seseorang menulis sebagai tanggapan atas kontribusi orang lain. Ini normal dan positif di banyak pengaturan online. Saya mencoba melakukannya dengan cara sesingkat mungkin, dengan alamat pribadi; tidak melihat ada yang salah dengan itu.
Andy Drucker
2
Konstruksi yang bagus! Saya punya pertanyaan: mari f menjadi fungsi indikator L ', dan h menjadi seperti dalam pertanyaan Gil. Sekarang, argumen Anda menunjukkan bahwa ia setuju dengan f pada y yang merupakan kata sandi resmi. Tapi bagaimana dengan y yang bukan kata sandi hukum?
Atau Meir
2
f