Sont randomisés algorithmes constructifs?

Question

De, les épreuves par la méthode probabiliste sont souvent dits non-constructive.

Cependant, une preuve par la méthode probabiliste conçoit en effet un algorithme aléatoire et l'utilise pour prouver l'existence. Cité de P103 de Randomized Algorithms Par Rajeev Motwani, Prabhakar Raghavan :

Nous pourrions voir la preuve par la méthode probabiliste comme une étude randomisée algorithme. Ce serait alors besoin d'une analyse plus poussée délimitant la probabilité que l'algorithme ne parvient pas à trouver une bonne partition sur un compte tenu de l'exécution. La principale différence entre une expérience de pensée la méthode probabiliste et un algorithme aléatoire est la fin qui chacun des rendements. Lorsque nous utilisons la méthode probabiliste, nous sommes seulement préoccupé de montrer l'existence d'un objet combinatoire; ainsi, nous se contentent de montrer qu'un événement se produit favorable à la non-zéro probabilité. Avec un algorithme aléatoire, d'autre part, l'efficacité est un facteur important - nous ne pouvons pas tolérer une miniscule probabilité de succès.

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

Comment est un algorithme ou une preuve être « constructif » défini?

Merci!

Answer 1

La méthode probabiliste est généralement utilisé pour montrer que la probabilité de certains objet aléatoire ayant une propriété est non nul, mais ne présente pas d'exemples. Il ne garantit qu'un algorithme « repeat-until-succès » finira par se terminer, mais ne donne pas une limite supérieure sur le moteur d'exécution. Donc, à moins que la probabilité d'une participation de propriété est importante, une preuve de l'existence par la méthode probabiliste rend un algorithme très faible.

En fait, les algorithmes probabilistes ne sont pas réellement constructives preuves d'existence, tant qu'ils sont des algorithmes à produits constructives preuves d'existence. La sortie est un objet du genre dont il était censé prouver l'existence de; mais le fait qu'il éventuellement un rendement ( « il existera une itération dans laquelle il donne un exemple - sauf avec une probabilité zéro ... ») ne suffit pas d'être constructif; il ne sera satisfaisante à quelqu'un qui accepte déjà que non-suffixes probabilité sans nulle construction d'existence. A l'inverse, si vous avez un bon lié au moment de l'exécution, alors il n'y a en principe aucune excuse pour ne pas l'exécuter afin de produire effectivement un exemple. Un bon algorithme probabiliste est toujours pas une preuve constructive, mais un bon plan pour obtenir une preuve constructive.

Notez que cette idée, qu'un algorithme aléatoire est une stratégie preuve (par opposition à une preuve en soi) pour démontrer une quantification existentielle, est un peu comme 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, que l'induction est essentiellement le cœur de récursion comme une technique de calcul. (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 à examiner si $ (n-1) ^ 2 Pour tout entier positif $ n $, $ est une somme des nombres impairs consécutifs précédant 2n-1 $, et ainsi de suite.) l'induction est essentiellement une preuve stratégie algorithmique que nous avons élevé un théorème, ce qui nous permet d'avoir la connaissance sans calculer explicitement chaque fois. Cependant, l'induction est acceptée de manière constructive car il est déjà un axiome (-schéma) de l'arithmétique de Peano, et qui est indépendant des autres axiomes. En revanche, il n'y a pas de règle d'inférence ou axiome qui permet à la méthode probabiliste de prouver l'existence constructive, ou de prouver de manière constructive que les algorithmes probabilistes produisent des preuves de l'existence, ou quoi que ce soit le long de ces lignes. Vous ne pouvez pas prouver qu'il existe des exemples d'une classe d'objet du fait qu'il existe un algorithme probabiliste pour le construire, à moins que vous acceptez déjà cette proposition, que ce soit comme un axiome, ou d'autres locaux.

Bien sûr, on pourrait adopter une position philosophique intermédiaire constructivisme et l'approche classique de l'existence, et dire que ce que l'on veut est pas des constructions en soi, mais la construction du schéma qui sont autorisés à échouer avec une probabilité inférieure à un; qui rendrait toute construction probabiliste « schématique », sinon tout à fait constructive. Où l'on souhaite tracer la ligne, de dire qu'ils trouvent une preuve de l'existence « satisfaisante », en fin de compte dépend de combien l'intuition (dans un sens non-philosophique) ils souhaitent gagner de preuves.

Answer 2

complexité preuve uniforme est un champ consacré (entre autres) à l'étude des notions constructives de preuves, et leur relation avec les classes de complexité. Pour chacun des populaires (uniformes) classes de complexité du circuit, on peut définir une théorie dans laquelle tout ce qui est prouvable a un « soutien » dans un algorithme dans cette classe de complexité. algorithmes probabilistes sont logés dans des versions du principe de pigeonhole (assez curieusement).

Malheureusement, je ne suis pas un expert, donc je ne peux pas dire beaucoup plus, autre que le point que vous le livre par Cook et Nguyen (même cuisinier que dans le théorème de Cook) et au travail de Emil Jerábek , en particulier sa sur le calcul aléatoire.