Les théorèmes naturels n'ont-ils été prouvés que «à haute probabilité»?

Il existe de nombreuses situations où une "preuve" randomisée est beaucoup plus facile qu'une preuve déterministe, l'exemple canonique étant le test d'identité polynomiale.

Question : Existe-t-il des "théorèmes" mathématiques naturels où une preuve randomisée est connue mais pas une preuve déterministe?

Par "preuve aléatoire" d'une déclaration $P$ je veux dire que

Il existe un algorithme randomisé qui prend une entrée $n > 0$ et si $P$ est faux produit une preuve déterministe de $\neg P$ avec une probabilité d'au moins $1-2^{-n}$ .
Quelqu'un a exécuté l'algorithme pour, disons, $n = 100$ , et n'a pas réfuté le théorème.

Il est facile de générer des déclarations non naturelles qui correspondent: choisissez simplement une grande instance de tout problème où seul un algorithme aléatoire efficace est connu. Cependant, bien qu'il y ait beaucoup de théorèmes mathématiques avec "beaucoup de preuves numériques", comme l'hypothèse de Riemann, je n'en connais aucun avec des preuves randomisées rigoureuses de la forme ci-dessus.

lo.logic randomness randomized-algorithms proofs Geoffrey Irving
la source

@Kaveh: Merci pour les corrections de catégorie. Je ne savais pas quoi mettre sous.

Geoffrey Irving

une autre direction, étudier la littérature sur la "dérandomisation" (à la recherche d'une bonne enquête également). le théorème de Reingold relativement récent (primé) n'était-il pas également le cas (encore avant la preuve)?

vzn

Eh bien, tout problème avec une preuve déterministe reposant sur l'ERH (comme Primes autrefois) aurait cette propriété

Suresh Venkat

Je suis désolé de le dire, mais je ne pense pas que votre question soit logique, car il ne peut y avoir de telles déclarations, naturelles ou non. Vous écrivez que N est un premier utilisé pour être un bon exemple mais (bien sûr) il y a toujours eu une preuve déterministe pour la primalité, juste un peu plus longtemps. Je ne peux pas non plus imaginer comment vous définiriez la probabilité de réussite d'un algorithme censé réfuter une instruction fixe. Peut-être que vous voulez demander une preuve efficace pour une classe de problèmes (c'est-à-dire que l'entrée serait P et n et l'énoncé P (n)) mais nous arrivons ensuite à la théorie de la complexité et à la définition de BPP.

domotorp

domotorp: Il est vrai que (en supposant que l'algorithme utilise un nombre limité de bits aléatoires), une telle preuve randomisée peut être dérandomisée avec un certain coût de performance. Cependant, je demande des exemples où le coût de performance est suffisamment élevé pour que la preuve déterministe n'ait pas été exécutée à ce jour, alors que la preuve randomisée l'a été. Je pense que les définitions ont un sens dans ce contexte.

Geoffrey Irving

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ Ce n'est pas un exemple de ce que vous demandez, mais cela suggère comment un tel exemple peut se produire. Certaines identités combinatoires peuvent être codées comme des identités sur des polynômes de degré borné . Si les polynômes sont univariés, pour prouver l'identité il suffit de la vérifier sur points. Cependant, si les polynômes sont multivariés et que le degré est au moins modérément grand, le lemme de Scwartz-Zippel peut être le seul moyen pratique de vérifier l'identité. $d$ $d+1$

Pour un exemple du cas univarié, consultez cet article de Zeilberger, résolvant une question de Knuth. Il prouve une déclaration sur les statistiques des permutations. Pour une permutation , soit le nombre des inversions de , et que le principal indice de $\pi \in S_n$ $\inv(\pi)$ $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ est la somme de tous les entiers de l'ensemble . Zeilberger prouve que, pour tout , la covariance des deux statistiques est $\pi$ $\{i: \pi(i+1) < \pi(i)\}$ $n$

où toutes les attentes sont supérieures à ununiformément aléatoiredans

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$

. La preuve de Zeilberger n'est qu'une vérification informatique pour

, et une observation que l'énoncé équivaut à une identité entre des polynômes en

de degré au plus

S_{n}

$S_n$

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

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

n

$n$

4

$4$

Sasho Nikolov
la source

Merci, c'est un bel article. J'aime bien la morale.

Geoffrey Irving

Les théorèmes naturels n'ont-ils été prouvés que «à haute probabilité»?

Réponses: