Les algorithmes randomisés sont-ils constructifs?

D'après, les preuves par la méthode probabiliste sont souvent dites non constructives.

Cependant, une preuve par méthode probabiliste conçoit en effet un algorithme aléatoire et l'utilise pour prouver l'existence. Cité de la p103 des algorithmes randomisés par Rajeev Motwani, Prabhakar Raghavan :

Nous pourrions voir la preuve par la méthode probabiliste comme un algorithme randomisé. Cela nécessiterait alors une analyse supplémentaire délimitant la probabilité que l'algorithme ne trouve pas une bonne partition sur une exécution donnée. La principale différence entre une expérience de pensée dans la méthode probabiliste et un algorithme randomisé est la fin que chacun donne. Lorsque nous utilisons la méthode probabiliste, nous voulons seulement montrer qu'il existe un objet combinatoire; ainsi, nous nous contentons de montrer qu'un événement favorable se produit avec une probabilité non nulle. Avec un algorithme randomisé, en revanche, l'efficacité est une considération importante - nous ne pouvons pas tolérer une probabilité de succès minuscule.

Je me demande donc si les algorithmes randomisés ne sont pas considérés comme constructifs, bien qu'ils produisent une solution à la fin de chaque exécution, ce qui peut ou non être une solution idéale.

Comment un algorithme ou une preuve étant "constructif" est-il défini?

Merci!

La méthode probabiliste est généralement utilisée pour montrer que la probabilité qu'un objet aléatoire ait une certaine propriété est non nulle, mais ne présente aucun exemple. Il garantit qu'un algorithme de "répétition jusqu'à la réussite" se terminera éventuellement, mais ne donne pas de limite supérieure lors de l'exécution. Donc, à moins que la probabilité d'une propriété ne soit substantielle, une preuve d'existence par la méthode probabiliste fait un très mauvais algorithme.

En fait, les algorithmes probabilistes ne sont pas réellement des preuves d'existence constructives, autant qu'ils sont des algorithmes pour produire des preuves d'existence constructives. La sortie est un objet du genre dont elle était censée prouver l'existence; mais le fait qu'il finira par en donner un ("il existera une itération dans laquelle il donnera un exemple - sauf avec une probabilité nulle ...") ne suffit pas pour être constructif; elle ne sera satisfaisante que pour quelqu'un qui accepte déjà qu'une probabilité sans zéro sans construction suffit à l'existence. Inversement, si vous avez une bonne limite d'exécution, il n'y a en principe aucune excuse pour ne pas l'exécuter afin de produire un exemple. Un bon algorithme probabiliste n'est toujours pas une preuve constructive, mais un bonprévoyez d'obtenir une preuve constructive.

Notez que cette idée, qu'un algorithme randomisé est une stratégie de preuve (par opposition à une preuve en soi) pour démontrer une quantification existentielle, n'est pas différente de l'idée que l'induction est une bonne stratégie de preuve pour montrer une quantification universelle (sur les nombres naturels ). Cette analogie peut sembler convaincante, car l'induction est essentiellement le cœur de la récursivité en tant que technique de calcul. (Pour tout entier positif$n$, si vous voulez décider si $n^2$ est une somme des nombres impairs consécutifs précédant $2n+1$, vous pouvez réduire cela à la recherche $(n-1)^2$ est une somme des nombres impairs consécutifs précédant $2n-1$, et ainsi de suite.) L'induction est essentiellement une stratégie de preuve algorithmique que nous avons élevée à un théorème, nous permettant d'avoir les connaissances sans les calculer explicitement à chaque fois. Cependant, l'induction est acceptée de manière constructive car elle est déjà un axiome (-scheme) de l'arithmétique de Peano, et un qui est indépendant des autres axiomes. En revanche, il n'y a pas de règle d'inférence ou d'axiome qui permet à la méthode probabiliste de prouver l'existence de manière constructive, ou de prouver de manière constructive que les algorithmes probabilistes produisent des preuves d'existence, ou quoi que ce soit dans ce sens. Vous ne pouvez tout simplement pas prouver qu'il existe des exemples d'une classe d'objets du fait qu'il existe un algorithme probabiliste pour le construire, à moins que vous n'acceptiez déjà cette proposition, soit comme un axiome, soit à partir d'autres prémisses.

Bien sûr, on pourrait adopter une position philosophique intermédiaire au constructivisme et à l'approche classique de l'existence, et dire que ce que l'on veut n'est pas des constructions en soi mais des schémas de construction qui peuvent échouer avec une probabilité inférieure à un; cela rendrait toute construction probabiliste "schématique", sinon complètement constructive. Là où l'on souhaite tracer la ligne, dire qu'ils trouvent une preuve d'existence «satisfaisante», dépend en fin de compte de l'intuition (au sens non philosophique) qu'ils souhaitent tirer des preuves.

La complexité de preuve uniforme est un domaine consacré (entre autres) à l'étude des notions constructives de preuves, et leur relation avec les classes de complexité. Pour chacune des classes de complexité de circuit (uniformes) populaires, on peut définir une théorie dans laquelle tout ce qui est prouvable a un "support" dans un algorithme de cette classe de complexité. Les algorithmes randomisés sont pris en charge par des versions du principe du pigeonhole (curieusement).

Malheureusement, je ne suis pas un expert, je ne peux donc pas en dire plus, à part vous indiquer le livre de Cook et Nguyen (même Cook que dans le théorème de Cook) et le travail d' Emil Jeřábek , en particulier sa thèse sur le calcul aléatoire.