Argumen untuk / terhadap dugaan Kolmogorov tentang kompleksitas sirkuit P

Menurut catatan sejarah (tidak terverifikasi), Kolmogorov berpikir bahwa setiap bahasa dalam $\mathsf{P}$ memiliki kompleksitas rangkaian linier. (Lihat sebelumnya pertanyaan dugaan Kolmogorov yang $P$ memiliki sirkuit linear-size .) Perhatikan bahwa kandungannya $\mathsf{P}\neq \mathsf{NP}$ .

Dugaan Kolmogorov, bagaimanapun, dipandang cenderung gagal. Sebagai contoh, Ryan Williams menulis dalam sebuah makalah baru-baru ini : "Dugaan itu akan mengejutkan, jika benar. Untuk bahasa dalam $\mathsf{P}$ membutuhkan $n^{100^{100}}$ waktu, tampaknya tidak mungkin bahwa kompleksitas masalah seperti itu akan secara ajaib menyusut ke ukuran $O(n)$ , hanya karena rangkaian yang berbeda dapat dirancang untuk setiap panjang input. "

Di sisi lain, Andrey Kolmogorov (1903-1987) secara luas diakui sebagai salah satu ahli matematika terkemuka abad ke-20. Agak sulit untuk membayangkan bahwa ia akan mengusulkan dugaan yang sepenuhnya absurd. Karena itu, untuk memahaminya dengan lebih baik, saya mencoba menemukan beberapa argumen yang mungkin sebenarnya mendukung dugaannya yang mengejutkan. Inilah yang bisa saya pikirkan:

$\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$ $L\in \mathsf{P}$ $L$

Ada dikenal eksplisit algoritma (mesin Turing) yang menerima . Dari sini kita dapat membangun keluarga fungsi eksplisit yang harus memiliki kompleksitas rangkaian superlinear. Namun, ini mungkin dipandang tidak mungkin, karena tidak ada yang dapat menemukan contoh seperti itu dalam lebih dari 60 tahun penelitian intensif tentang sirkuit. $L$
Tidak ada dikenal eksplisit algoritma untuk . Sebagai contoh, keberadaannya dibuktikan melalui cara-cara yang tidak konstruktif, seperti Aksioma Pilihan. Atau, bahkan jika algoritma eksplisit ada, tidak ada yang dapat menemukannya. Namun, mengingat bahwa ada banyak bahasa tanpa batas yang dapat memainkan peran , tidak mungkin lagi bahwa mereka semua berperilaku dengan cara yang tidak ramah ini. $L$ $L$

Tetapi kemudian, jika kita menganggap kedua opsi itu tidak mungkin, satu-satunya kemungkinan yang tersisa adalah bahwa seperti itu tidak ada. Itu berarti , yang tepatnya merupakan dugaan Kolmogorov. $L$ $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$

Pertanyaan: Dapatkah Anda memikirkan argumen lebih lanjut untuk / terhadap dugaan Kolmogorov?

cc.complexity-theory circuit-complexity ho.history-overview Andras Farago
sumber

Saya bertanya-tanya: Apakah kita memiliki kandidat untuk menyangkal dugaan Kolmogorov? Tentu saja, orang dapat mempertimbangkan masalah yang terbukti memiliki kompleksitas super linier. Mungkin beberapa dari mereka lebih cenderung tidak memiliki sirkuit ukuran linear?

Bruno

mari kita hadapi itu, tidak ada yang memiliki petunjuk sedikit pun. (ulang kutipan goldman di hollywood: "tidak ada yang tahu apa-apa.") dugaan (tidak dipublikasikan) mungkin telah dibuka bahkan lebih lama dari P =? NP. namun, ide / sudut yang kasar perlu ditelusuri: teori kompresi & kompresibilitas. ini pada dasarnya apa yang disinggung oleh williams dan mungkin bisa menjadi jantung dari banyak pemisahan kelas kompleksitas. idenya adalah bahwa ada cara dasar / algoritma untuk menyandikan data, dan beberapa pola secara intrinsik lebih sulit untuk dikompres menggunakan penyandian (sembarang) . tetapi tampaknya ada sedikit hasil di bidang ini juga.

vzn

dan btw, banyak koneksi kompleksitas Kolmogorov ke kompleksitas komputasi misalnya dieksplorasi oleh Fortnow mungkin memiliki beberapa koneksi penjelasan mengapa pertanyaan begitu sulit untuk diselesaikan, karena begitu banyak pertanyaan terkait kompleksitas Kolmogorov tidak dapat diputuskan ...?

vzn

@ Bruno: Saya kira masalah

-complete akan menjadi kandidat yang baik, misalnya Pemrograman Linier atau Masalah Nilai Sirkuit. Jika

maka masalah-masalah ini tidak dapat diselesaikan bahkan secara tidak seragam dalam ukuran-poli dan kedalaman-logaritmik, sehingga setidaknya tampaknya masuk akal untuk menebak bahwa masalah-masalah seperti itu seharusnya tidak dapat dipecahkan dalam ukuran linier (dan kedalaman tidak terbatas) baik . Penentu mungkin kandidat yang masuk akal lainnya. Tapi ini hanya proposal - Saya tidak punya alasan kuat untuk berpikir mereka memiliki ukuran sirkuit super linier.

P

$\mathsf{P}$

P ⊈ N C

$\mathsf{P} \not\subseteq \mathsf{NC}$

Joshua Grochow

Jawaban:

Catatan kaki dari makalah saya yang Anda kutip merujuk pada "argumen" heuristik juga, setidaknya, apa yang kita pikirkan adalah intuisi Kolmogorov - resolusi positif dari masalah ketiga belas Hilbert.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

Secara khusus, dibuktikan oleh Kolmogorov dan Arnold bahwa setiap fungsi kontinu pada variabel dapat dinyatakan sebagai komposisi fungsi "sederhana": penambahan dua variabel, dan fungsi kontinu pada satu variabel. Oleh karena itu, atas "dasar" fungsi kontinu satu variabel dan penambahan dua variabel, setiap fungsi kontinu pada variabel memiliki "kompleksitas sirkuit" . $n$ $O(n^2)$ $n$ $O(n^2)$

Tampaknya Kolmogorov percaya ada analog diskrit, di mana " variabel kontinu dalam " menjadi "Boolean dalam variabel dan poli waktu komputasi", dan di mana "dasar" yang diberikan di atas menjadi fungsi Boolean dua variabel. $n$ $n$ $(n)$

Ryan Williams
sumber

Akan sangat menarik jika analog diskrit yang diyakini Kolmogorov memang ada. Agaknya, peneliti telah mencoba untuk menemukannya, karena dapat menyebabkan sejauh bukti

. Apa hambatan utama yang mereka temui?

P \neq N P

$P\neq NP$

Andras Farago

Penghadang jalan? Saya tidak berpikir ada orang yang telah menemukan jalan :) Karena kebanyakan orang percaya bahwa

tidak memiliki

sirkuit ukuran, untuk setiap tetap

, mungkin beberapa orang bahkan mencari jalan.

P

$P$

O (n^{k})

$O(n^k)$

k

$k$

Ryan Williams

Jawaban Stasys pada pertanyaan sebelumnya memberikan beberapa intuisi yang berpotensi menguntungkan: /cstheory//a/22048/8243 . Saya akan mencoba untuk menyatakan kembali di sini seperti yang saya mengerti. Intuisi kuncinya adalah untuk melihat sirkuit sebagai, bukan algoritma, tetapi suatu pengkodean dari suatu set (set itu menerima). Kita bisa mendapatkan batas atas pada ukuran pengkodean dengan algoritma running time (yaitu, menerjemahkan time- TM ke dalam sirkuit size- ), tetapi tidak jelas apa hubungan sebaliknya yang harus ada. Jika bahasa dalam , maka mungkin ini menyiratkan bahwa keanggotaan "lokal" cukup untuk dikodekan dengan sangat singkat. $t$ $t$ $\mathsf{P}$

Yaitu, keanggotaan dalam adalah pernyataan tentang waktu berjalan suatu algoritma sedangkan sirkuit linier adalah (mungkin) pernyataan tentang ukuran pengodean set kata-kata dengan panjang tetap. Keduanya pernyataan tentang kesederhanaan bahasa tetapi mereka hidup di dunia yang mungkin sangat berbeda. $\mathsf{P}$

Intuisi lain Stasys menyebutkan berasal dari "string indikator" dari suatu bahasa, yang mari kita formalkan sebagai string tanpa batas di mana bit adalah jika string leksikografis ke- ada dalam bahasa dan sebaliknya. A (polytime) TM untuk bahasa adalah oracle (cepat) untuk string --- diberikan dalam biner, menghasilkan bit ke- . Sirkuit (berukuran linier) untuk input dengan panjang adalah oracle (ringkas) untuk awalan panjang - dari string. Dugaan itu menjadi "string tanpa batas yang memiliki oracle 'cepat' memiliki awalan-oracle 'ringkas'." $j$ $1$ $j$ $0$ $j$ $j$ $n$ $2^n$

Tidak satu pun dari penjelasan di atas yang menjelaskan mengapa dan" linear "mungkin merupakan parameter yang tepat untuk masing-masing pernyataan, tetapi saya pikir mereka menunjukkan bahwa satu intuisi alami - bahwa sirkuit bertindak seperti algoritma, dan algoritma yang lebih rumit memerlukan sirkuit yang sama rumitnya - mungkin menyesatkan. $``\mathsf{P}"$

usul
sumber