Dugaan Kolmogorov bahwa

Dalam bukunya, Boolean Function Complexity, Stasys Jukna menyebutkan (halaman 564) bahwa Kolmogorov percaya bahwa setiap bahasa di P memiliki sirkuit dengan ukuran linier. Tidak ada referensi yang disebutkan dan saya tidak dapat menemukan apa pun secara online. Apakah ada orang yang tahu lebih banyak mengenai hal ini?

cc.complexity-theory reference-request circuit-complexity ho.history-overview Hamid
sumber

Paging @Stasys :)

Suresh Venkat

lihat juga ini di sini rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small

T ....

"Dugaan" Kolmogorov ini hanya rumor. Tentu saja tidak ada yang diterbitkan atau lebih. Di bekas USSR, matematika "penerbitan" berarti sesuatu yang berbeda: berbicara di seminar, atau memberi tahu kolega Anda saat makan siang, atau yang lain. Menghitung kertas bukan masalah. Jadi, saya tidak bisa mengesampingkan bahwa "dugaan" ini hanya diberitahukan kepada Levin oleh Kolmogorov saat mereka berjalan ke sebuah seminar di MGU (Universitas Moskow). (Sebenarnya, aku juga memerintahkan cara matematika ini.) Jadi, jangan menganggap ini terlalu serius - hanya sebagai "rumor", yang (tentu saja) belum dibantah selama bertahun-tahun ...

Stasys

@vzn

untuk setiap

diperbaiki karena

. Yang terakhir ini diperkuat ke

oleh teorema Kannan.

P \subseteq s i z e (n^{k}) \Rightarrow P \neq N P

$\mathsf{P} \subseteq \mathsf{size}(n^k) \Rightarrow \mathsf{P} \neq \mathsf{NP}$

k

$k$

\forall k \in N : Σ_{4}^{P} ⊈ s i z e (n^{k})

$\forall k \in \mathbb{N}: \Sigma_4^{\mathsf{P}} \not \subseteq \mathsf{size}(n^k)$

Σ_{2}^{P}

$\Sigma_2^{\mathsf{P}}$

Sasho Nikolov

@Stasys, Anda harus memposting itu sebagai jawaban sehingga pertanyaannya menjadi terjawab (sehingga situs tidak akan terus menabraknya ke halaman depan).

Kaveh

Jawaban:

[Mengikuti saran Kaveh, saya menempatkan komentar saya (agak diperluas) sebagai jawaban]

"Dugaan" Kolmogorov ini hanya rumor. Itu tidak dipublikasikan di mana pun. Di bekas USSR, matematika "penerbitan" memiliki arti yang berbeda dari apa yang dilakukan hari ini: berbicara di seminar atau memberi tahu kolega Anda saat makan siang. Menghitung kertas bukan masalah. (Sebenarnya, saya juga telah memerintahkan cara melakukan matematika ini.) Saya tidak bisa mengesampingkan kemungkinan bahwa "dugaan" ini hanya diperintahkan kepada Levin oleh Kolmogorov saat mereka berjalan ke sebuah seminar di Universitas Moskow. Jadi jangan menganggap ini terlalu serius sebagai dugaan formal; itu hanya rumor yang (tidak perlu dikatakan) tidak dibantah selama bertahun-tahun. Tapi karena raksasa seperti Kolmogorov serius memikirkan masalah ini, dan belum mengecualikan kemungkinan "kekuatan iblis", dugaan itu harus diperlakukan dengan cukup serius,

Berikut adalah spekulasi (sangat, sangat kasar) dari pemahaman saya tentang dugaan ini. Intuisi kami (yang tampaknya salah) tentang cara kerja sirkuit bergantung pada melihat perhitungan oleh suatu program sebagai proses berurutan yang secara bertahap mengumpulkan informasi tentang string input. Intuisi ini dipinjam dari pandangan kami tentang cara kerja mesin Turing. Tetapi setiap string input menentukan subcircuit (menyaksikan atau ). Dan untuk rangkaian yang benar, sudah cukup bahwa himpunan subcircuit untuk dan $x$ $f(x)=1$ $f(x)=0$ $f^{-1}(1)$ terpisah. Yaitu, sirkuit adalah "pengkodean lokal" kompak dari partisi -cube. Panjang kode ini adalah kompleksitas Kolmogorov dari string biner yang diberikan panjang . Algoritmawaktu polinomial, bagaimanapun, melakukan lebih banyak: ia memberikansatu"pengkodean global" dari seluruh string tanpa batas untuk semua . Sekarang, string tanpa batas memungkinkan pengodean ukuran $f^{-1}(0)$ $n$ $f_n$ $2^n$ $f$ $n$ $f$ $n^c$ harus "sederhana", dan awalannya "harus" memungkinkan penyandian "lokal" yang lebih ringkas. Tentu saja, itu tetap menjadi misteri mengapa Kolmogorov berpikir bahwa "lokal" encoding bahkan ukuran untuk beberapa maka mungkin cukup ... $cn$ $c$

PS Maaf, lupa menambahkan: Sebuah konfirmasi yang sangat baik dari "tesis" saya bahwa sirkuit harus dilihat sebagai kode (statis) daripada algoritma (dinamis) adalah teorema terkenal David Barrington bahwa seluruh kelas dapat disimulasikan oleh polinomial -ukuran program percabangan lebar 5. Pandangan "mengumpulkan informasi" di sini benar-benar salah: bahkan tidak jelas bagaimana menghitung fungsi mayoritas dengan hanya menyimpan 5 bit informasi. Gagasan pintar David hanya untuk menyandikan $NC^1$ perilaku formula yang diberikan oleh urutan 5-permutasi tertentu, dan untuk menunjukkan bahwa string yang diterima dan ditolak akan mendapatkan kode yang berbeda. Intinya adalah bahwa program percabangan juga tidak "menghitung" --- itu lebih mengkodekan string input oleh sub-programnya: ketika input tiba, tepi yang tidak konsisten menghilang, dan kami memiliki kode input ini.

Stasys
sumber

Adakah contoh bahasa non-sepele yang mendukung dugaan ini?

Igor Shinkar

@ Igor: Saya tidak tahu. Beberapa indikasi (lemah) disebutkan di sini . Sebenarnya, saya cenderung menjawab GMB: kemungkinan besar, dugaan itu dirangsang oleh solusi mereka terhadap masalah Hilbert ke-13, bukan dengan pertimbangan kombinatorial.

Stasys

Saya sama sekali tidak memiliki pengetahuan tentang topik ini seperti Stasys, tapi saya mendengar pembenaran yang berbeda untuk dugaan ini yang mungkin saya bagikan juga.

Saya mendengar bahwa dugaan itu didasarkan pada solusi positif untuk Masalah Ketigabelas Hilbert, yang diselesaikan bersama oleh Komolgorov dan muridnya Arnold. Teorema (yang jauh lebih umum daripada masalah yang dinyatakan Hilbert) mengatakan:

Setiap fungsi kontinu dari sejumlah variabel terbatas dapat diekspresikan sebagai komposisi hingga dari fungsi variabel tunggal, serta sejumlah terbatas aplikasi dari operator biner . $+$

Saya diberitahu bahwa, berdasarkan pada beberapa detail implementasi dari bukti teorema ini, ini dapat dilihat sebagai analog berkelanjutan dari klaim bahwa . $\exists k \, \, \, P \subset SIZE(n^k)$

Maaf saya tidak memenuhi syarat untuk lebih tepatnya dari ini - jika ada orang lain yang mendengar ide ini, mungkin mereka bisa membantu saya.

GMB
sumber

dapatkah kamu memberikan

referensi

@ GMB: diamati dengan baik - ini bisa menjadi penjelasan yang lebih dekat untuk alasan munculnya dugaan itu.

Stasys