Natürliche Theoreme haben sich nur "mit hoher Wahrscheinlichkeit" bewährt?

Es gibt viele Situationen, in denen ein randomisierter "Beweis" viel einfacher ist als ein deterministischer Beweis, wobei das kanonische Beispiel das Testen der polynomischen Identität ist.

Frage : Gibt es natürliche mathematische "Theoreme", bei denen ein randomisierter Beweis bekannt ist, ein deterministischer Beweis jedoch nicht?

Mit einem "randomisierten Beweis" einer Aussage meine ich das $P$

Es gibt einen randomisierten Algorithmus, der eine Eingabe von annimmt. Wenn falsch ist, wird ein deterministischer Beweis für mit einer Wahrscheinlichkeit von mindestens . $n > 0$ $P$ $\neg P$ $1-2^{-n}$
Jemand hat den Algorithmus beispielsweise für und den Satz nicht widerlegt. $n = 100$

Es ist einfach, nicht-natürliche Aussagen zu generieren, die passen: Wählen Sie einfach eine große Instanz eines Problems aus, bei dem nur ein effizienter randomisierter Algorithmus bekannt ist. Obwohl es viele mathematische Theoreme mit "vielen numerischen Beweisen" gibt, wie die Riemannsche Hypothese, kenne ich keine mit strengen randomisierten Beweisen der obigen Form.

lo.logic randomness randomized-algorithms proofs Geoffrey Irving
quelle

@Kaveh: Danke für die Kategoriekorrekturen. Ich war mir nicht sicher, unter was ich es stellen sollte.

Geoffrey Irving

eine andere Richtung, das Studium der "Derandomisierungs" -Literatur (auf der Suche nach einer guten Übersicht). War der relativ neue (preisgekrönte) Reingold-Satz nicht auch ein Fall davon (wieder vor dem Beweis)?

vzn

Nun, jedes Problem mit einem deterministischen Beweis, der auf der ERH beruht (wie es früher bei Primes der Fall war), hätte diese Eigenschaft

Suresh Venkat,

Es tut mir leid, das zu sagen, aber ich glaube nicht, dass Ihre Frage Sinn macht, da es keine solchen Aussagen geben kann, natürlich oder nicht. Sie schreiben, dass N eine Primzahl ist, die früher ein gutes Beispiel war, aber (natürlich) es gab immer einen deterministischen Beweis für die Ursprünglichkeit, nur ein bisschen länger. Ich kann mir auch nicht vorstellen, wie Sie die Erfolgswahrscheinlichkeit eines Algorithmus definieren würden, der eine feste Aussage widerlegen soll. Vielleicht möchten Sie nach einem effizienten Beweis für eine Klasse von Problemen fragen (dh die Eingabe wäre P und n und die Aussage P (n)), aber dann kommen wir zur Komplexitätstheorie und der Definition von BPP.

Domotorp

domotorp: Es ist wahr, dass (unter der Annahme, dass der Algorithmus eine begrenzte Anzahl von Zufallsbits verwendet) ein solcher randomisierter Beweis mit einigen Leistungskosten derandomisiert werden kann. Ich frage jedoch nach Beispielen, bei denen die Leistungskosten so hoch sind, dass der deterministische Beweis bisher nicht durchgeführt wurde, während der randomisierte Beweis dies getan hat. Ich halte die Definitionen in diesem Zusammenhang für sinnvoll.

Geoffrey Irving

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ Dies ist kein Beispiel dafür, wonach Sie fragen, aber es zeigt, wie ein solches Beispiel zustande kommen kann. Einige kombinatorische Identitäten können als Identitäten über Polynome mit begrenztem Grad codiert werden . Wenn die Polynome univariant sind, genügt es, sie mit Punkten zu verifizieren, um die Identität zu beweisen . Wenn die Polynome jedoch multivariat sind und der Grad mindestens mäßig groß ist, ist das Scwartz-Zippel-Lemma möglicherweise die einzige praktische Möglichkeit, die Identität zu überprüfen. $d$ $d+1$

Ein Beispiel für den univariaten Fall finden Sie in diesem Artikel von Zeilberger zur Lösung einer Frage von Knuth. Er beweist eine Aussage über die Statistik von Permutationen. Für eine Permutation sei die Zahl von Inversionen von , und lassen Sie den Hauptindex von $\pi \in S_n$ $\inv(\pi)$ $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ ist die Summe aller ganzen Zahlen in der Menge . Zeilberger beweist, dass für alle die Kovarianz der beiden Statistiken ist $\pi$ $\{i: \pi(i+1) < \pi(i)\}$ $n$

dem alle Erwartungen über einen gleichmäßig zufälligenin. Zeilbergers Beweis ist nur eine Computerüberprüfung fürund eine Beobachtung, dass die Aussage einer Identität zwischen Polynomen invon höchstensGraden entspricht.

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
quelle

Danke, das ist ein schöner Artikel. Ich mag die Moral.

Geoffrey Irving

Natürliche Theoreme haben sich nur "mit hoher Wahrscheinlichkeit" bewährt?

Antworten: