Sirkuit batas bawah dan kompleksitas kolmogorov

Pertimbangkan alasan berikut:

Misalkan menunjukkan kompleksitas Kolmogorov dari string . Teorema ketidaklengkapan Chaitin mengatakan itu $K(x)$ $x$

untuk konsisten dan cukup kuat resmi sistem , terdapat konstan (tergantung hanya pada sistem formal dan bahasanya) sehingga untuk setiap string , tidak dapat membuktikan bahwa . $S$ $T$ $x$ $S$ $K(x) \geq T$

Biarkan menjadi fungsi Boolean pada variabel st kompleksitas Kolmogorov spektrumnya paling banyak . Misalkan menjadi kompleksitas sirkuit , yaitu ukuran komputasi sirkuit minimal . $f_n$ $n$ $k$ $S(f_n)$ $f_n$ $f_n$

A (kasar) terikat atas untuk adalah untuk konstanta dan adalah fungsi berang-berang yang sibuk (langkah maksimum yang mungkin dilakukan penghentian Mesin Turing dengan deskripsi ukuran dapat melakukan). (Untuk setiap dalam spektrum, buat minterm dari penetapan kebenaran yang sesuai, dan ambil ATAU dari semua minterm ini.) $S(f_n)$

S (f_{n}) \leq c \cdot B B (k) \cdot n

$S(f_n)\leq c\cdot BB(k) \cdot n$

c

$c$

B B (k)

$BB(k)$

k

$k$

1

$1$

Misalkan sekarang untuk keluarga tak terbatas dari fungsi Boolean , kami memiliki bukti formal bahwa memerlukan sirkuit ukuran superlinear, yaitu $L = \{f_n\}_{n}$ $L$

S ⊢ \forall n \geq n_{0}, g (n) \cdot n \leq S (f_{n})

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$ mana .

g (n) \in ω (1)

$g(n)\in \omega(1)$

Jika kita mengambil menjadi cukup besar, kita akan memiliki $n$

g (n) > c \cdot B B (T)

$g(n) > c\cdot BB(T)$

Secara khusus ini akan menjadi bukti bahwa kompleksitas Kolmogorov dari spektrum $f_n$ setidaknya $T$ , yang tidak mungkin.

Ini mengarah pada dua pertanyaan:

1) Seharusnya ada yang salah dalam alasan di atas. Terutama karena itu akan membuat sirkuit batas bawah lebih rendah secara formal tidak dapat dibuktikan.

2) Apakah Anda tahu pendekatan serupa untuk menunjukkan hambatan untuk batas bawah, yaitu, menunjukkan bahwa jenis batas bawah (sirkuit) tertentu secara formal tidak dapat dibuktikan?

cc.complexity-theory reference-request lo.logic circuit-complexity kolmogorov-complexity Magnus Find
sumber

ide yang menarik. agak terkait dengan bukti razborov / rudich kembali "bukti alami" yang membuat sketsa hambatan untuk P =? NP (tetapi juga mungkin berlaku untuk pemisahan kelas kompleksitas lainnya seperti yang tercantum dalam contoh di kertas) .. sudahkah Anda membaca makalah itu? lihat juga hambatan P =? NP dan kompleksitas / hambatan sirkuit monoton . nampaknya mengisyaratkan bahwa pemisahan kelas kompleksitas memiliki struktur yang mirip dengan bukti yang tidak dapat dibuktikan.

vzn

dapatkah Anda menguraikan "spektrum" dari f_n? adakah cara untuk mengutarakan pertanyaan tanpa merujuk pada "spektrum"?

vzn

mungkin benar bahwa seseorang dapat mempelajari kompleksitas fungsi dengan mempelajari TM terkecil [dalam arti table state / state] yang menghitungnya dan bahwa ini kira-kira akan cocok dengan batas bawah sirkuit. jika Anda dapat menunjukkan bahwa tidak mungkin, daripada benar-benar sulit, untuk menemukan TM terkecil itu, Anda mungkin memiliki sesuatu di sana. namun itu "sederhana" untuk menemukan TM terkecil melalui enumerasi kanonik sirkuit atau TM. jika Anda merenungkan mengapa pendekatan ini berhasil, mungkin membantu untuk memahami mengapa pertanyaan itu tidak mengarah pada masalah.

vzn

Kanan. Terima kasih untuk referensi. Saya tahu tentang makalah Natural Proofs. Saya tidak tahu apakah pertanyaan itu dapat dirumuskan tanpa "spektrum". Yang saya maksud dengan "spektrum" adalah urutan

(f (0, 0, . ., 0), f (0, 0, . ., 1), . ., f (1, 1, . ., 1))

$(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$

Magnus Find

Jawaban:

Tidak ada yang salah dengan argumen Anda, tetapi tidak ada kontradiksi. Anda membuktikan bahwa dari beberapa cukup besar kompleksitas Kolmogorov dari spektrum selalu setidaknya . Tetapi pernyataan ini sepele benar! Meskipun kita tidak dapat membuktikan bahwa kompleksitas Kolmogorov dari satu string besar, jika kita memiliki urutan, maka dari beberapa titik itu harus mengandung hanya string kompleksitas besar. Jadi, yang kamu dapat? Harus memenuhi , berapakah angka yang tidak dapat kita hitung (karena $N$ $f_n$ $T$ $N$ $N>g^{-1}(c \cdot BB(T))$ ), jadi tidak ada masalah sama sekali. $BB$

domotorp
sumber

Terima kasih. Saya jatuh ke dalam perangkap percaya bahwa seseorang dapat "memilih" beberapa nilai N cukup besar, tetapi ketika Anda menunjukkan ini tidak mungkin dalam

, dan seperti yang Anda juga tunjukkan dengan benar, ini sebenarnya akan berlaku untuk setiap keluarga meningkatkan urutan.

S

$S$

Magnus Find

Ini adalah situasi bermasalah yang lebih sederhana. Misalkan menjadi string pertama (dalam urutan leksikografis) sedemikian rupa sehingga ; string seperti itu terbukti ada untuk semua . Kemudian . $A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

Penyebabnya mungkin karena sistem formal tidak dapat menghitung . $BB(T)$

Sunting: Ini adalah situasi bermasalah "lebih eksplisit". Biarkan menjadi panjang maksimal string yang kompleksitas Kolmogorov-nya paling banyak ; terbukti ada. Kemudian . $\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(k)+1}) > k$

Yuval Filmus
sumber

Mengapa situasi ini bermasalah? Anda tidak memberikan program yang outputnya akan menjadi A (k) dan panjangnya akan kurang dari k.

domotorp

Saya memiliki kebingungan yang sama dengan Domotor, tetapi saya setuju bahwa satu masalah dengan alasan OP adalah bahwa sistem formal tidak akan dapat membuktikan batas atas pada

untuk

cukup besar .

B B (k)

$BB(k)$

k

$k$

Sasho Nikolov

Ini bermasalah dalam (bisa dibilang) pengertian yang sama dengan pertanyaan awal.

Yuval Filmus

Saya masih belum mengerti. Anda tidak menunjukkan string dan bukti bahwa kompleksitas Kolmogorov-nya besar. Anda menunjukkan bukti bahwa ada string yang kompleksitasnya besar.

Sasho Nikolov

Saya pikir mereka bermasalah dalam berbagai cara. Ketika saya membacanya, Anda menunjuk pada pernyataan benar yang spesifik, yang tidak memiliki bukti. Ketika saya menjelaskannya dalam pertanyaan saya, saya menunjukkan bahwa hal itu memerlukan bukti dari sesuatu yang tidak dapat dibuktikan.

Magnus Find