¿Son constructivos los algoritmos aleatorios?

A partir de, las pruebas por el método probabilístico a menudo se dice que no son constructivas.

Sin embargo, una prueba por método probabilístico de hecho diseña un algoritmo aleatorio y lo usa para probar la existencia. Citado de p103 de Algoritmos aleatorizados por Rajeev Motwani, Prabhakar Raghavan :

Podríamos ver la prueba por el método probabilístico como un algoritmo aleatorio. Esto requeriría un análisis adicional que limite la probabilidad de que el algoritmo no encuentre una buena partición en una ejecución dada. La principal diferencia entre un experimento mental en el método probabilístico y un algoritmo aleatorio es el final que cada uno produce. Cuando usamos el método probabilístico, solo nos preocupa mostrar que existe un objeto combinatorio; por lo tanto, nos contentamos con mostrar que ocurre un evento favorable con probabilidad distinta de cero. Con un algoritmo aleatorio, por otro lado, la eficiencia es una consideración importante: no podemos tolerar una probabilidad de éxito minúscula.

Entonces, me pregunto si los algoritmos aleatorios se consideran no constructivos, aunque generan una solución al final de cada ejecución, que puede ser o no una solución ideal.

¿Cómo se define un algoritmo o prueba que es "constructivo"?

¡Gracias!

El método probabilístico se usa típicamente para mostrar que la probabilidad de que algún objeto aleatorio tenga una determinada propiedad no es cero, pero no muestra ningún ejemplo. Sí garantiza que un algoritmo de "repetición hasta el éxito" terminará eventualmente, pero no proporciona un límite superior en el tiempo de ejecución. Entonces, a menos que la probabilidad de tener una propiedad sea sustancial, una prueba de existencia por el método probabilístico hace un algoritmo muy pobre.

De hecho, los algoritmos probabilísticos no son en realidad pruebas de existencia constructivas, sino que son algoritmos para producir pruebas de existencia constructivas. La salida es un objeto del tipo del que se pretendía demostrar la existencia de; pero el hecho de que eventualmente producirá uno ("existirá una iteración en la que dará un ejemplo, excepto con probabilidad cero ...") no es suficiente para ser constructivo; solo será satisfactorio para alguien que ya acepte que la probabilidad distinta de cero sin construcción es suficiente para la existencia. Por el contrario, si tiene un buen límite en el tiempo de ejecución, entonces, en principio, no hay excusa para no ejecutarlo para realmente producir un ejemplo. Un buen algoritmo probabilístico todavía no es una prueba constructiva, sino una buenaplan para obtener una prueba constructiva.

Tenga en cuenta que esta idea, que un algoritmo aleatorio es una estrategia de prueba (en oposición a una prueba en sí misma) para demostrar una cuantificación existencial, no es diferente a la idea de que la inducción es una buena estrategia de prueba para mostrar una cuantificación universal (sobre los números naturales) ) Esta analogía puede parecer convincente, ya que la inducción es esencialmente el corazón de la recursividad como técnica computacional. (Para cualquier entero positivo$n$, si quieres decidir si $n^2$ es una suma de los números impares consecutivos que preceden $2n+1$, puede reducir esto a investigar si $(n-1)^2$ es una suma de los números impares consecutivos que preceden $2n-1$, y así sucesivamente.) La inducción es esencialmente una estrategia de prueba algorítmica que hemos elevado a un teorema, lo que nos permite tener el conocimiento sin computarlo explícitamente cada vez. Sin embargo, la inducción se acepta de manera constructiva porque ya es un axioma (-esquema) de la aritmética de Peano, y uno que es independiente de los otros axiomas. Por el contrario, no existe una regla de inferencia o axioma que permita que el método probabilístico demuestre la existencia de manera constructiva, o que demuestre constructivamente que los algoritmos probabilísticos producen pruebas de existencia, o algo por el estilo. Simplemente no puede probar que hay ejemplos de una clase de objeto por el hecho de que existe un algoritmo probabilístico para construirlo, a menos que ya acepte esa proposición, ya sea como un axioma o desde otras premisas.

Por supuesto, uno podría adoptar una posición filosófica intermedia al constructivismo y el enfoque clásico de la existencia, y decir que lo que uno quiere no son construcciones per se, sino esquemas de construcción que pueden fallar con una probabilidad menor que uno; eso haría que cualquier construcción probabilística fuera "esquemática", si no completamente constructiva. Cuando se desea trazar la línea, decir que encuentran una prueba de existencia "satisfactoria", en última instancia, depende de cuánta intuición (en un sentido no filosófico) desean obtener de las pruebas.

La complejidad de la prueba uniforme es un campo dedicado (entre otros) al estudio de las nociones constructivas de las pruebas y su relación con las clases de complejidad. Para cada una de las clases de complejidad de circuito populares (uniformes), se puede definir una teoría en la que todo lo que es demostrable tiene un "respaldo" en un algoritmo en esta clase de complejidad. Los algoritmos aleatorios se acomodan a través de versiones del principio de casillero (por extraño que parezca).

Desafortunadamente, no soy un experto, así que no puedo decir mucho más, aparte de señalarle el libro de Cook y Nguyen (el mismo Cook que en el teorema de Cook) y el trabajo de Emil Jeřábek , especialmente su tesis sobre computación aleatoria.