Teorema alami terbukti hanya "probabilitas tinggi"?

Ada banyak situasi di mana "bukti" acak jauh lebih mudah daripada bukti deterministik, contoh kanonik adalah pengujian identitas polinomial.

Pertanyaan : Apakah ada "teorema" matematika alamiah di mana bukti acak diketahui tetapi bukti deterministik tidak?

Dengan "bukti acak" dari pernyataan $P$ saya maksudkan itu

Ada algoritma acak yang mengambil input $n > 0$ dan jika $P$ salah menghasilkan bukti deterministik $\neg P$ dengan probabilitas setidaknya $1-2^{-n}$ .
Seseorang telah menjalankan algoritma untuk, katakanlah, , dan tidak menyanggah teorema. $n = 100$

Sangat mudah untuk menghasilkan pernyataan non-alami yang cocok: cukup pilih contoh besar dari masalah di mana hanya algoritma acak yang efisien yang diketahui. Namun, meskipun ada banyak teorema matematika dengan "banyak bukti numerik", seperti hipotesis Riemann, saya tidak mengetahui adanya bukti acak yang akurat dari bentuk di atas.

lo.logic randomness randomized-algorithms proofs Geoffrey Irving
sumber

@Kaveh: Terima kasih atas koreksi kategori. Saya tidak yakin apa yang harus dimasukkan.

Geoffrey Irving

arah lain, mempelajari literatur "derandomisasi" (mencari survei yang baik juga). Bukankah teorema Reingold yang relatif baru (memenangkan penghargaan) juga merupakan kasusnya (sekali lagi sebelum pembuktian)?

vzn

Nah masalah dengan bukti deterministik bertumpu pada ERH (seperti Primes dulu) akan memiliki properti ini

Suresh Venkat

Saya minta maaf untuk mengatakan tetapi saya tidak berpikir pertanyaan Anda masuk akal, karena tidak ada pernyataan seperti itu, wajar atau tidak. Anda menulis bahwa N adalah bilangan prima yang digunakan untuk menjadi contoh yang baik tetapi (tentu saja) selalu ada bukti deterministik juga untuk keutamaan, hanya sedikit lebih lama. Saya juga tidak bisa membayangkan bagaimana Anda akan menentukan probabilitas keberhasilan suatu algoritma yang seharusnya menyangkal satu pernyataan perbaikan. Mungkin Anda ingin meminta bukti yang efisien untuk kelas masalah (yaitu, inputnya adalah P dan n dan pernyataan P (n)) tetapi kemudian kita sampai pada teori kompleksitas dan definisi BPP.

domotorp

domotorp: Memang benar bahwa (dengan asumsi algoritma menggunakan jumlah bit acak terbatas) bukti acak seperti itu dapat derandomized dengan beberapa biaya kinerja. Namun, saya bertanya tentang contoh-contoh di mana biaya kinerja cukup tinggi sehingga bukti deterministik belum berjalan sampai saat ini, sedangkan bukti acak miliki. Saya percaya definisi ini masuk akal dalam konteks ini.

Geoffrey Irving

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ Ini bukan contoh dari apa yang Anda minta, tetapi ini menunjukkan bagaimana contoh seperti itu bisa terjadi. Beberapa identitas kombinatorial dapat dikodekan sebagai identitas tentang polinomial derajat terikat . Jika polinomialnya univariat, untuk membuktikan identitasnya cukup dengan memverifikasi pada poin. Namun, jika polinomialnya multivarian, dan tingkatannya setidaknya cukup besar, lemma Scwartz-Zippel mungkin satu-satunya cara praktis untuk memverifikasi identitas. $d$ $d+1$

Untuk contoh kasus univariat, periksa artikel ini oleh Zeilberger, menyelesaikan pertanyaan Knuth. Dia membuktikan pernyataan tentang statistik permutasi. Untuk permutasi , misalkan menjadi angka dari inversi , dan biarkan indeks utama dari $\pi \in S_n$ $\inv(\pi)$ $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ menjadi jumlah semua bilangan bulat di set . Zeilberger membuktikan bahwa, untuk semua , kovarian dari dua statistik adalah $\pi$ $\{i: \pi(i+1) < \pi(i)\}$ $n$

di mana semua harapan lebih dari satu seragam acakdi. Bukti Zeilberger hanyalah verifikasi komputer untuk, dan pengamatan bahwa pernyataan itu setara dengan identitas antara polinomial dalamderajat paling banyak.

E [(inv (π) - E [inv (π)]) \cdot (maj (π) - E [maj (π)])] = \frac{1}{4} (\binom{n}{2}),

$\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},$

π

$\pi$

S_{n}

$S_n$

n \in {1, 2, 3, 4, 5}

$n \in \{1, 2, 3, 4, 5\}$

n

$n$

4

$4$

Sasho Nikolov
sumber

Terima kasih, itu artikel yang bagus. Saya cukup suka moral.

Geoffrey Irving

Teorema alami terbukti hanya "probabilitas tinggi"?

Jawaban: