Naturalne twierdzenia udowodnione tylko „z dużym prawdopodobieństwem”?

Istnieje wiele sytuacji, w których zrandomizowany „dowód” jest znacznie łatwiejszy niż dowód deterministyczny, którego kanonicznym przykładem jest testowanie tożsamości wielomianowej.

Pytanie : Czy istnieją jakieś naturalne „twierdzenia” matematyczne, w których znany jest dowód losowy, ale dowód deterministyczny nie?

Przez „losowy dowód” stwierdzenia rozumiem to $P$

Istnieje algorytm randomizowany, który przyjmuje dane wejściowe a jeśli jest fałszem, to deterministyczny dowód z prawdopodobieństwem co najmniej . $n > 0$ $P$ $\neg P$ $1-2^{-n}$
Ktoś uruchomił algorytm dla, powiedzmy, i nie obalił twierdzenia. $n = 100$

Łatwo jest wygenerować nienaturalne instrukcje, które pasują: wystarczy wybrać dużą instancję dowolnego problemu, w którym znany jest tylko wydajny algorytm losowy. Chociaż jednak istnieje wiele twierdzeń matematycznych z „dużą ilością dowodów numerycznych”, takich jak hipoteza Riemanna, nie znam żadnych z rygorystycznymi przypadkowymi dowodami powyższej postaci.

lo.logic randomness randomized-algorithms proofs Geoffrey Irving
źródło

@Kaveh: Dzięki za poprawki kategorii. Nie byłem pewien, co to podłożyć.

Geoffrey Irving

inny kierunek, studiowanie literatury na temat „derandomizacji” (także w poszukiwaniu dobrej ankiety). czy stosunkowo niedawne (nagradzane) twierdzenie Reingolda nie było również tego przypadkiem (ponownie przed dowodem)?

vzn

Cóż, każdy problem z deterministycznym dowodem spoczywającym na ERH (jak kiedyś Primes) miałby tę właściwość

Suresh Venkat

Przykro mi to mówić, ale nie sądzę, aby twoje pytanie miało sens, ponieważ nie ma takich stwierdzeń, naturalnych czy nie. Piszesz, że N jest liczbą pierwszą, która była dobrym przykładem, ale (oczywiście) zawsze istniał deterministyczny dowód na pierwszeństwo, tylko trochę dłużej. Nie wyobrażam sobie również, jak zdefiniowałbyś prawdopodobieństwo powodzenia algorytmu, który powinien obalić jedną instrukcję fix. Być może chcesz poprosić o skuteczny dowód na pewną klasę problemów (tzn. Dane wejściowe to P i n oraz stwierdzenie P (n)), ale potem dochodzimy do teorii złożoności i definicji BPP.

domotorp

domotorp: Prawdą jest, że (zakładając, że algorytm używa ograniczonej liczby losowych bitów), każdy taki randomizowany dowód może zostać zdegradowany z pewnym kosztem wydajności. Pytam jednak o przykłady, w których koszt wydajności jest na tyle wysoki, że dowód deterministyczny nie był do tej pory uruchamiany, a dowód losowy tak. Uważam, że definicje mają sens w tym kontekście.

Geoffrey Irving

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ $d$ $d+1$ punktach . Jeśli jednak wielomiany są wielowymiarowe, a stopień jest co najmniej umiarkowanie duży, lemat Scwartza-Zippela może być jedynym praktycznym sposobem weryfikacji tożsamości.

Aby zapoznać się z przykładem przypadku jednoczynnikowego, zapoznaj się z tym artykułem Zeilbergera, rozwiązującym pytanie Knutha. Udowadnia stwierdzenie o statystykach permutacji. Dla permutacji $\pi \in S_n$ $\inv(\pi)$ $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ $\pi$ $\{i: \pi(i+1) < \pi(i)\}$ $n$

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
źródło

Dzięki, to piękny artykuł. Całkiem podoba mi się moralność.

Geoffrey Irving

Naturalne twierdzenia udowodnione tylko „z dużym prawdopodobieństwem”?

Odpowiedzi: