Bisakah keacakan benar (terbukti) diganti dengan keacakan Kolmogorov untuk RP?

Apakah ada upaya untuk menunjukkan bahwa keacakan Kolmogorov akan cukup untuk RP ? Apakah probabilitas yang digunakan dalam pernyataan "Jika jawaban yang benar adalah YA, maka (mesin Turing probabilistik) mengembalikan YA dengan probabilitas ..." selalu didefinisikan dengan baik dalam kasus itu? Atau akankah hanya ada batas atas dan bawah untuk probabilitas itu? Atau akankah selalu ada beberapa mesin Turing probabilistik, yang probabilitasnya akan didefinisikan dengan baik (atau setidaknya batas bawah yang seharusnya lebih besar dari 1/2)?

Kelas RP di sini relatif arbitrer, dan orang juga bisa mengajukan pertanyaan ini untuk gagasan lemah (pseudo-) keacakan daripada keacakan Kolmogorov. Tapi keacakan Kolmogorov tampaknya menjadi titik awal yang baik.

Memahami kata "probabilitas" akan menjadi bagian dari upaya untuk menunjukkan bahwa keacakan Kolmogorov bekerja untuk RP. Namun, izinkan saya mencoba menggambarkan satu pendekatan yang mungkin, untuk memperjelas apa artinya, dan mengapa saya berbicara tentang batas atas dan bawah:

Mari $s$ menjadi (Kolmogorov random) string. Biarkan $A$ menjadi mesin Turing probabilistik yang diberikan sesuai dengan bahasa dari RP. Jalankan $A$ dengan $s$ sebagai sumber untuk bit acak $n$ kali, terus mengkonsumsi bit yang sebelumnya tidak dikonsumsi dari $s$ satu demi satu.

Untuk $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$ $p_+^s:=\limsup_{n\to\infty}p_n^s$ $p_-^s:=\liminf_{n\to\infty}p_n^s$ $p_+^s$ $p_-^s$ $s$ $p_+^s=p_-^s$ $s$ $p_-^{s_1}=p_-^{s_2}$ $s_1$ $s_2$ $p\geq 1/2$ $p\leq p_-^s$ $s$

randomized-algorithms randomness pseudorandomness Thomas Klimpel
sumber

Saya tidak mengerti pertanyaannya. Apa yang Anda maksud dengan "konsep keacakan> sudah cukup untuk <kelas kompleksitas>"? RP dapat derandomisasi dalam waktu polinomial dengan oracle untuk string acak Kolmogorov, jika itu yang Anda tanyakan.

Emil Jeřábek

Saya tidak mengerti apa yang Anda maksud dengan mengatakan bahwa RP akan “bekerja”, dan saya tidak mengerti komentar terakhir Anda (mesin RP selalu berhenti setelah banyak langkah secara polinomi, baik secara definisi, atau tanpa kehilangan generalisasi jika menggunakan ketidaknyamanan. definisi).

Emil Jeřábek

Dalam pertanyaan itu sendiri, saya juga tidak mengerti apa yang Anda maksud dengan "probabilitas" ketika berbicara tentang string acak Kolomogorov. Tidak seperti "string acak" biasa, yang diambil dari distribusi acak, menjadi Kolmogorov acak adalah properti ya-tidak aktual yang diberikan atau tidak dimiliki string. Jadi, apakah string seperti itu membuat algoritma menerima bukan variabel acak, dan karena itu tidak ada artinya untuk bertanya tentang kemungkinannya.

Emil Jeřábek

Pendekatan yang masuk akal untuk ini adalah dengan mengambil perspektif "konstruktif Martingales" dari string algoritmik-acak. Secara khusus, orang mungkin berharap bahwa jika gagal menipu , maka ini akan diterjemahkan menjadi "prediktor bit berikutnya" untuk , dan kemudian ke dalam strategi taruhan yang menunjukkan bahwa tidak acak. Saya tidak tahu apakah pendekatan ini, bahkan jika berhasil, akan memberikan tingkat konvergensi yang bermakna untuk dan ; Namun, tampaknya ada pendekatan yang lebih tua untuk mempelajari kelas kompleksitas (kata kunci: "ukuran sumber daya terbatas") yang menggunakan ide ini, jadi ada beberapa harapan.

s

$s$

A

$A$

s

$s$

s

$s$

p_{+}

$p_+$

p_{-}

$p_-$

Andrew Morgan

Tautan Wikipedia yang relevan (yang memiliki referensi lebih lanjut) untuk komentar saya sebelumnya: Martingales konstruktif (lihat definisi ketiga), dan ukuran yang terbatas sumber daya

Andrew Morgan

Jawaban:

Saya pikir pertanyaan yang diajukan di sini kira-kira " apakah ada perasaan di mana kita dapat mengganti urutan bit acak dalam suatu algoritma dengan bit yang diambil secara deterministik dari string acak Kolmogorov yang panjang? " Ini setidaknya pertanyaan yang akan saya coba untuk menjawab! (Jawaban singkatnya adalah "Ya, tetapi hanya jika Anda memperbesar probabilitas kesalahan terlebih dahulu")

Iya...

Kita tentu bisa mengatakan sesuatu di sini. Biarkan menjadi beberapa bahasa dan biarkan menjadi algoritma yang mengambil input dan string acak (distribusi seragam lebih dari ) st . Dengan kata lain, adalah algoritma yang keliru dengan probabilitas paling banyak . $L$ $A$ $x$ $r\in U_{f(|x|)}$ $\{0,1\}^{f(|x|)}$ $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$ $A$ $\epsilon(\cdot)$

Perhatikan sekarang bahwa jika memberikan jawaban yang salah pada yaitu, , ini memberi kita beberapa cara untuk menggambarkan , khususnya, kita dapat menggambarkannya sebagai -th string yang menyebabkan salah padaUntuk melakukan ini, kita cukup membuat mesin yang memiliki kode , , , dan sedikit , dan hanya menyebutkan pilihan dari sampai menemukan pilihan ke- dari sedemikian rupa sehingga . $A$ $(x,r)$ $A(x,r)\not=L(x)$ $r$ $i$ $A$ $x.$ $x$ $A$ $i$ $b=1\iff x\in L$ $r'$ $\{0,1\}^{f(|x|)}$ $i$ $r'$ $A(x,r')\not= b$

Jadi sekarang kita tahu bahwa kita dapat memanfaatkan menjadi pilihan string acak yang buruk menjadi deskripsi, mari kita amati beberapa kondisi yang cukup untuk mengubah deskripsi menjadi kompresi. Untuk menggambarkan , kita memerlukan bit yang cukup untuk menggambarkan , , , dan kemudian kode untuk prosedur kita (kode untuk dan rutin yang kita uraikan), memberikan sebagai deskripsi panjang $r$ $r$ $x$ $i$ $b$ $A$

| x | + | i | + O (1) = | x | + \log_{2} (2^{f (| x |)} ϵ (x)) + O (1) = | x | + f (| x |) - \log (1 / ϵ (x)) + O (1) .

$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$

Ingat bahwa adalah panjang , jadi ini adalah kompresi if misalnya, ketika . $r$ $f(|x|)$ $r$

\log (1 / ϵ (x)) = | x | + ω (1),

$\log(1/\epsilon(x)) = |x|+\omega(1),$

ϵ (x) = 1 / 2^{2 | x |}

$\epsilon(x)=1/2^{2|x|}$

Akhirnya, amati bahwa jika adalah string acak Kolmogorov, maka kita tidak dapat memiliki kompresi seperti itu, sehingga selama probabilitas kesalahan cukup kecil, string acak Kolmogorov menggantikan urutan bit acak akan menyebabkan menjawab benar! $r$ $A$ $A$

Perhatikan bahwa satu-satunya hal yang kami manfaatkan tentang adalah probabilitas kesalahannya kecil. Kami tidak peduli jika memiliki waktu yang sangat lama atau jika memiliki kesalahan satu atau dua sisi. $A$ $A$ $A$

Membawa ini kembali ke pertanyaan (atau atau ), ini mengatakan bahwa selama kita memperbesar probabilitas kesalahan dari algoritma kita, kita dapat menggunakan string acak Kolmogorov sebagai ganti bit acak mereka. $RP$ $coRP$ $BPP$

... Tetapi hanya jika kita memperkuat dulu.

Pertanyaan tindak lanjut mungkin adalah "bisakah saya melakukan ini tanpa memperbesar kemungkinan kesalahan?" Pertimbangkan algoritma berikut yang menentukan dan memiliki probabilitas kesalahan . $A$ $\{0,1\}^*$ $1/2^n$

Pada input : $x$

Hasilkan string $r\in\{0,1\}^n$
Jika , tolak. $r=x$
Menerima.

$r$ $x$ $A$ $x$ $r$ $x$ $A$

Catatan tentang sumber: Saya tidak yakin apakah ini novel, tapi saya memasukkan argumen pertama dalam langganan saya untuk ujian kualifikasi saya yang akhirnya akan tersedia online setelah saya selesai merevisinya.

Dylan McKay
sumber

Teman saya Preetum menunjukkan kekonyolan pengkodean mesin dan memutuskan ketika kita bukan hanya dapat mengkodekan sedikit yang mengatakan apakah atau tidak . Saya akan mengedit jawaban untuk mencerminkan ini.

M

$M$

M (x)

$M(x)$

x \in L

$x\in L$

Dylan McKay

Mike Sipser menggunakan sejenis argumen kompresi dalam makalah kerennya sciencedirect.com/science/article/pii/0022000088900359 (perhatikan bahwa grafik expander yang ia butuhkan memang dibuat secara eksplisit dl.acm.org/citation.cfm?id=273915 )

Ryan Williams