¿Son constructivos algoritmos aleatorizados?

Question

De, a menudo se dice que las pruebas del método probabilístico no son restringidas.

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

Podríamos ver la prueba mediante el método probabilístico como un algoritmo aleatorizado. Esto requeriría un análisis adicional que limita 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 aleatorizado es el final que cada uno produce. Cuando usamos el método probabilístico, solo nos preocupa demostrar que existe un objeto combinatorio; Por lo tanto, estamos contentos con demostrar que un evento favorable ocurre con una probabilidad no cero. Con un algoritmo aleatorizado, por otro lado, la eficiencia es una consideración importante: no podemos tolerar una probabilidad de éxito minúsculo.

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

¿Cómo se define un algoritmo o prueba "constructiva"?

¡Gracias!

Answer 1

El método probabilístico se usa típicamente para mostrar que la probabilidad de alguno El objeto aleatorio que tiene una determinada propiedad no es cero, pero no exhibe ningún ejemplo. Asesora que un algoritmo de "repetición hasta el éxito" finalmente terminará, pero no da un límite superior en el tiempo de ejecución. Entonces, a menos que la probabilidad de una propiedad de 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 a producir Pruebas de existencia constructiva. La salida es un objeto del tipo que estaba destinado a probar la existencia; Pero el hecho de que lo hará finalmente El rendimiento uno ("existirá una iteración en la que produce un ejemplo, excepto con probabilidad cero ...") no es suficiente para ser constructivo; Solo será satisfactorio para alguien que ya acepta que la no probabilidad 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 producir realmente un ejemplo. Un buen algoritmo probabilístico todavía no es una prueba constructiva, sino una buena plan para obtener una prueba constructiva.

Tenga en cuenta que esta idea, que un algoritmo aleatorizado es un Estrategia de prueba (A diferencia de 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 recursión como una técnica computacional. (Para cualquier número entero positivo $ n $, si desea 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 a $ 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 calcularlo explícitamente cada vez. Sin embargo, la inducción se acepta de manera constructiva porque ya es un axioma (-scheme) de aritmética de maní, 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 demuestre constructivamente que los algoritmos probabilísticos producen pruebas de existencia, o cualquier cosa en este sentido. Simplemente no puede probar que hay ejemplos de una clase de objeto del hecho de que existe un algoritmo probabilístico para construirlo, a menos que ya acepte esa proposición, ya sea como axioma o de otras premisas.

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

Answer 2

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

Desafortunadamente no soy un experto, así que no puedo decir mucho más, aparte de señalarte el libro por Cook y Nguyen (mismo cocinero que en el teorema de Cook) y para el trabajo de Emil Jeřábek, especialmente su tesis en cálculo aleatorizado.