Os algoritmos aleatórios são construtivos?

Desde então, as provas pelo método probabilístico são frequentemente consideradas não construtivas.

No entanto, uma prova pelo método probabilístico de fato projeta um algoritmo aleatório e o utiliza para provar a existência. Citado na página 103 de Algoritmos Aleatórios Por Rajeev Motwani, Prabhakar Raghavan :

Poderíamos ver a prova pelo método probabilístico como um algoritmo aleatório. Isso exigiria uma análise mais aprofundada, limitando a probabilidade de o algoritmo não encontrar uma boa partição em uma determinada execução. A principal diferença entre um experimento mental no método probabilístico e um algoritmo aleatório é o fim que cada um produz. Quando usamos o método probabilístico, estamos preocupados apenas em mostrar que existe um objeto combinatório; portanto, nos contentamos em mostrar que um evento favorável ocorre com probabilidade diferente de zero. Por outro lado, com um algoritmo aleatório, a eficiência é uma consideração importante - não podemos tolerar uma minúscula probabilidade de sucesso.

Então, eu me pergunto se os algoritmos aleatórios são vistos como não construtivos, embora eles produzam uma solução no final de cada execução, que pode ou não ser uma solução ideal.

Como é definido um algoritmo ou prova "construtivo"?

Obrigado!

O método probabilístico é normalmente usado para mostrar que a probabilidade de algum objeto aleatório ter uma determinada propriedade é diferente de zero, mas não apresenta nenhum exemplo. Ele garante que um algoritmo de "repetir até o sucesso" acabe eventualmente, mas não fornece um limite superior no tempo de execução. Portanto, a menos que a probabilidade de uma propriedade seja substancial, uma prova de existência pelo método probabilístico cria um algoritmo muito ruim.

De fato, algoritmos probabilísticos não são, na verdade, provas construtivas de existência, tanto quanto são algoritmos para produzir provas construtivas de existência. A saída é um objeto do tipo que deveria provar a existência de; mas o fato de que acabará por produzir um ("existirá uma iteração na qual dará um exemplo - exceto com probabilidade zero ...") não é suficiente para ser construtivo; só será satisfatório para alguém que já aceite que a probabilidade não-zero-sem-construção é suficiente para a existência. Por outro lado, se você tem um bom limite no tempo de execução, então não há desculpa para não executá-lo para produzir um exemplo. Um bom algoritmo probabilístico ainda não é uma prova construtiva, mas uma boaplano para obter uma prova construtiva.

Observe que essa idéia, que um algoritmo aleatório é uma estratégia de prova (em oposição a uma prova em si) para demonstrar uma quantificação existencial, não é diferente da idéia de que a indução é uma boa estratégia de prova para mostrar uma quantificação universal (acima dos números naturais ) Essa analogia pode parecer convincente, pois a indução é essencialmente o coração da recursão como uma técnica computacional. (Para qualquer número inteiro positivo$n$, se você quiser decidir se $n^2$ é uma soma dos números ímpares consecutivos que precedem $2n+1$, você pode reduzir isso para investigar se $(n-1)^2$ é uma soma dos números ímpares consecutivos que precedem $2n-1$e assim por diante.) A indução é essencialmente uma estratégia de prova algorítmica que elevamos a um teorema, permitindo-nos ter o conhecimento sem explicitamente calculá-lo a cada vez. Entretanto, a indução é aceita construtivamente porque já é um axioma (esquema) da aritmética Peano e independente dos outros axiomas. Por outro lado, não existe uma regra de inferência ou axioma que permita ao método probabilístico provar a existência construtivamente, ou provar construtivamente que os algoritmos probabilísticos produzem provas da existência, ou qualquer coisa nesse sentido. Você simplesmente não pode provar que há exemplos de uma classe de objeto pelo fato de existir um algoritmo probabilístico para construí-lo, a menos que você já aceite essa proposição, como um axioma ou de outras premissas.

Certamente, pode-se adotar uma posição filosófica intermediária ao construtivismo e à abordagem clássica da existência, e dizer que o que se quer não são construções em si, mas esquemas de construção que podem falhar com uma probabilidade menor que uma; isso tornaria qualquer construção probabilística "esquemática", se não completamente construtiva. Onde se deseja traçar a linha, dizer que eles acham uma prova de existência "satisfatória", em última análise, depende de quanta intuição (em um sentido não filosófico) eles desejam obter com as provas.

A complexidade uniforme da prova é um campo dedicado (entre outros) ao estudo de noções construtivas de provas e sua relação com as classes de complexidade. Para cada uma das classes populares (uniformes) de complexidade de circuitos, pode-se definir uma teoria na qual tudo o que é provável tem um "respaldo" em um algoritmo nessa classe de complexidade. Algoritmos aleatórios são acomodados através de versões do princípio pigeonhole (por incrível que pareça).

Infelizmente, não sou especialista, por isso não posso dizer muito mais, além de apontar o livro de Cook e Nguyen (o mesmo Cook que no teorema de Cook) e o trabalho de Emil Jeřábek , especialmente sua tese sobre computação aleatória.