Bukti bahwa batas atas sirkuit untuk

18

Dalam deskripsi masalah Clay resmi untuk P versus NP dinyatakan bahwa akan mengikuti dari yang menunjukkan bahwa "setiap bahasa dalam [kelas bahasa dikenali dalam waktu eksponensial dengan mesin Turing deterministik] dapat dihitung oleh keluarga sirkuit Boolean sedemikian rupa sehingga untuk setidaknya satu , memiliki gerbang lebih sedikit daripada maksimum yang dibutuhkan untuk menghitung fungsi Boolean apa pun . " Namun, satu-satunya referensi adalah bahwa ini "adalah pengamatan yang menarik oleh V. Kabanets." Bisakah seseorang tolong tunjukkan saya ke versi yang diterbitkan dari implikasi ini dengan bukti? $P \neq NP$ $E$ $<B_n>$ $n$ $B_n$ $f: \{0,1\}^n \longrightarrow \{0,1\}$

cc.complexity-theory circuit-complexity David
sumber

25

Saya tidak berpikir makalah dalam jawaban lain berisi jawaban untuk pertanyaan Anda. Memang saya tidak begitu yakin bukti telah dipublikasikan, karena hasilnya mengikuti dari hasil terkenal lainnya.

Bukti pernyataan yang Anda inginkan adalah sebagai berikut:

berisi fungsi kompleksitas sirkuit maksimum yang mungkin pada setiap panjang input, dengan hanya mendefinisikan fungsi yang membuktikan dirinya (menggunakan pergantian) berbeda dari semua fungsi dengan kompleksitas sirkuit non-maksimum. Ini standar dan ide buktinya dapat ditemukan di sumber-sumber seperti buku teks Arora dan Barak. $\Sigma_3 E$
Jika maka , dengan padding dan runtuhnya waktu hirarki polinomial untuk . $P = NP$ $\Sigma_3 E = E$ $P$
Karena itu jika maka ada bahasa di dengan kompleksitas rangkaian maksimum. Ini adalah alat kontras dari apa yang ingin Anda buktikan. $P = NP$ $E$

Ryan Williams
sumber

Bagus, saya kira Anda akan menjadi orang pertama yang menjawabnya.

Mohammad Al-Turkistany

4

Ada juga jawaban di koran Kabanets dan Cai. Dalam Teorema 10 mereka membuktikan bahwa jika

ada di

, maka

berisi keluarga fungsi Boolean dari kompleksitas rangkaian maksimum. Jika

, maka

dan

, maka, oleh Teorema,

memang mengandung bahasa dengan kompleksitas maksimum.

M C S P

$MCSP$

P

$P$

E^{N P}

$E^{NP}$

P = N P

$P=NP$

M C S P \in P

$MCSP\in P$

E^{N P} = E

$E^{NP}=E$

E

$E$

Andras Farago

1

Poin bagus, Andras! Salah satu pengukur dalam bagian

dapat dilihat sebagai pemecahan MCSP.

Σ_{3} E

$\Sigma_3 E$

Ryan Williams

6

googling sekitar menemukan saya makalah ini yang diterbitkan dengan referensi di bawah ini.

Masalah minimisasi sirkuit

Valentine Kabanets dan Jin-Yi Cai

Kami mempelajari kompleksitas masalah minimisasi rangkaian: dengan tabel kebenaran fungsi Boolean f dan parameter s, tentukan apakah f dapat diwujudkan dengan ukuran sirkuit Boolean paling banyak di s. Kami berdebat mengapa masalah ini tidak mungkin ada di P (atau bahkan di P / poly) dengan memberikan sejumlah konsekuensi mengejutkan dari asumsi tersebut. Kami juga berpendapat bahwa membuktikan masalah ini sebagai NP-lengkap (jika memang benar) akan menyiratkan membuktikan rangkaian kuat batas bawah untuk kelas E, yang muncul di luar teknik yang dikenal saat ini.

Ini tampaknya diterbitkan di bawah ini.

diperpanjang abstrak dalam Prosiding Simposium ACM Tahunan ke Tiga Puluh Dua tentang Teori Komputasi (STOC'00), halaman 73-79, 2000. laporan teknis, dalam Kolokium Elektronik tentang Kompleksitas Komputasi TR99-045, 1999. http: // www. cs.sfu.ca/~kabanets/Research/circuit.html
diperpanjang abstrak dalam Prosiding Simposium ACM Tahunan ke Tiga Puluh Dua tentang Teori Komputasi (STOC'00), halaman 73-79, 2000. http://eccc.hpi-web.de/report/1999/045/

Joshua Herman
sumber

Perhatikan bahwa jawaban ini tidak menjawab pertanyaan di atas tetapi memberikan referensi dari mana pertanyaan ini berasal.

Joshua Herman

Bukti bahwa batas atas sirkuit untuk

Jawaban: