Nominaría el teorema de PCP más famoso. Echemos un breve vistazo a esto:
El siguiente extracto es una copia directa y pegada de esto: http: //people.csail.mit.edu/dmos…, con un pequeño giro al final agregado para reflexionar sobre.
En la década de 1970, el panorama de la investigación de algoritmos cambió dramáticamente. Se descubrió que un algoritmo eficiente para cualquiera de los numerosos problemas algorítmicos de aspecto inocente implicaría algo que suena demasiado fantástico para ser verdad: un algoritmo que, dado un enunciado matemático demostrable, encuentra eficientemente la prueba más corta para el enunciado. Para obtener una estimación de cuán fantástico es este último, dicho algoritmo, si existe, actualmente vale al menos $ 6,000,000, promovido por el Instituto Clay para quien resuelva seis problemas matemáticos centrales; $ 1 millón de dólares por problema. El algoritmo habría resuelto eficientemente los seis problemas. Divertidamente, uno de los seis problemas es determinar si existe tal algoritmo. Este problema se conoce como el problema P vs. NP.
- En el problema del embalaje del contenedor (BPP), ¿por qué el primer ajuste decreciente (FFD) es más eficiente que el primer ajuste creciente (FFI)?
- ¿Dónde nos llevará la investigación genómica impulsada por la informática en 5 años?
- ¿Cuáles son algunos lenguajes dinámicos de grado de investigación?
- ¿Qué tipo de servicio de limpieza necesitas?
- ¿Cuáles son los pasos para hacer captura de movimiento?
Por otro lado, parece que los problemas algorítmicos de aspecto inocente mencionados anteriormente podrían haber tenido fácilmente un algoritmo eficiente: son increíblemente similares a los problemas para los que sí conocemos algoritmos eficientes. Un ejemplo es Max-Cut: encuentre la mejor manera de separar los nodos de una red en dos, de modo que haya tantos enlaces como sea posible entre las dos partes. Si reemplaza “tantos” por “tan poco”, obtendrá Min-Cut, cuyo algoritmo basado en el flujo es estudiado por todos los estudiantes de informática hasta el día de hoy. Un algoritmo eficiente para Max-Cut, por otro lado, implicaría el algoritmo con un valor de $ 6,000,000, o, en términos técnicos, Max-Cut es “NP-hard”.
Pasaron algunos años, y los investigadores observaron algo interesante: aunque en realidad no encontraron algoritmos eficientes para problemas como Max-Cut, a veces pudieron probar que ciertos algoritmos no funcionarán mucho peor que lo óptimo para los problemas. Por ejemplo, aquí hay una manera de generar una partición Max-Cut de modo que el número de enlaces entre las dos partes sea al menos la mitad del máximo (en términos técnicos, esto es una “aproximación de 1/2”): seleccione la partición al azar. Es decir, para cada nodo lanza una moneda. Si la moneda muestra “caras”, coloque el nodo en la primera parte, y si la moneda muestra “colas”, coloque el nodo en la segunda parte. La probabilidad de que los dos puntos finales de un enlace pertenezcan a partes diferentes es exactamente la mitad. Por lo tanto, en promedio, la mitad de todos los enlaces conectarán nodos que pertenecen a diferentes partes. Como resultado, hay un mejor algoritmo para Max-Cut, uno que encuentra una partición en la que la fracción de enlaces entre diferentes partes es aproximadamente 0.878 veces la óptima (es decir, una aproximación de 0.878). Este algoritmo fue descubierto por Michel Goemans y David Williamson en la década de 1990 y no lo describiremos aquí. Ese algoritmo no se ha mejorado en las últimas dos décadas.
Si bien Max-Cut tiene una aproximación dentro de un factor constante, para otros problemas no se encontraron tales aproximaciones; a veces la mejor aproximación dependía del tamaño de la entrada, por lo que a medida que el tamaño de la entrada crecía, la aproximación empeoraba. En agudo contraste, algunos problemas podrían aproximarse arbitrariamente bien (dentro de 0.9999..9 para cualquier número de 9). Esto dejó a los investigadores preguntándose si estaban lejos de los otros problemas: ¿podrían existir mejores algoritmos de aproximación que no se hubieran descubierto? La salvación vino de una fuente inesperada.
A principios de la década de 1990, los investigadores se dieron cuenta de cómo mostrar la dureza NP de los problemas de aproximación. Esto explica el poco éxito que tuvieron los algoritmos algoritmos al mejorar sus aproximaciones para algunos problemas.
El camino conceptual que condujo a este avance fue largo y entrelazado. Comenzó una década antes con trabajos de Goldwasser, Micali y Rackoff sobre pruebas de conocimiento cero, y un trabajo de Babai sobre pruebas interactivas. En aquel entonces, nadie previó que esto podría tener implicaciones para los algoritmos de aproximación, pero esto es lo que terminó sucediendo.
Ambos trabajos sugirieron modelos para probar y verificar pruebas que eran diferentes del modelo estándar de escribir una prueba y verificarla paso a paso. Los nuevos modelos veían la demostración del teorema como una discusión entre un probador y un verificador. El verificador puede hacer preguntas prover, y las preguntas pueden ser aleatorizadas. Si la impresión del verificador de la validez de la prueba es correcta con probabilidad, digamos, 0.99, dijeron, esto es suficientemente bueno.
Esos modelos y modelos relacionados se convirtieron en el tema de estudio y clasificación que mostraron que eran sorprendentemente poderosos. Esta investigación finalmente creó el conocimiento que condujo a la dureza de la aproximación.
– Entonces, ¿qué implica la dureza de la aproximación? “Simplemente” el siguiente teorema que nadie que haya escrito o verificado una prueba matemática consideraría posible, pero que sin embargo resulta ser cierto:
“Cada prueba matemática se puede escribir en un formato que se pueda verificar probabilísticamente leyendo solo dos declaraciones (sin importar cuántas declaraciones haya en la prueba)”.
Una prueba estándar de tamaño n es una secuencia de declaraciones, ordenadas 1, …, n. Cada declaración está implícita en algunas de las declaraciones anteriores y las premisas. La última declaración es lo que queremos probar. Es importante destacar que la única forma de asegurarse de que la última declaración sea correcta utilizando la prueba estándar es seguir el razonamiento, declaración por declaración. Si hay un error en cualquiera de las implicaciones, la declaración puede estar equivocada.
En contraste, en el nuevo formato de prueba, muchas declaraciones pueden implicar la misma declaración. Por ejemplo, es posible que la declaración en la 5ª posición determine la declaración en la 10ª posición, pero también que la declaración en la 16ª posición determine la declaración en la 10ª posición. Esta estructura hace posible la siguiente propiedad de “robustez”: incluso si solo se mantiene una pequeña fracción de todas las implicaciones en el nuevo formato, todavía se puede deducir el razonamiento completo de la prueba original.
Esta propiedad de robustez hace posible la comprobación probabilística: para verificar la prueba, uno elige un par de posiciones aleatorias de modo que se suponga que la declaración en la primera posición implica la declaración en la segunda posición. Luego se prueba que este es el caso. Para una prueba correcta, la primera afirmación implica la segunda. Por otro lado, si el resultado final de la prueba es falso, es decir, no hay razonamiento que lo implique, entonces casi todas las implicaciones no deben ser válidas. Por lo tanto, la probabilidad de que la primera afirmación implique la segunda es baja.
El teorema se conoció como el teorema de PCP, donde PCP significa “Pruebas probabilísticamente comprobables”.
Por cierto, como algunos lectores pueden reconocer, PCP también significa “fenilciclohexil piperidina”, una droga disociativa recreativa. Según MuliSafra, un investigador que participó en la prueba de una de las primeras versiones del teorema de PCP, el nombre conmemora un incidente en el que una fuerza policial sospechó erróneamente que Safra y sus amigos tenían un laboratorio de PCP. Safra pensó que lo menos que podían hacer después de ser acusados falsamente es ejecutar un laboratorio de PCP (aunque de otra naturaleza).
Para completar la imagen, expliquemos cómo PCP es relevante para la dureza de la aproximación.
Suponga que desea probar una dureza de aproximación de 0.95 para Max-Cut. Afirmamos que habrá terminado si muestra lo siguiente: dada una red, es NP- difícil distinguir entre el caso donde hay una partición de los nodos en dos conjuntos, de modo que una fracción X de todos los enlaces está entre diferentes partes, y el caso donde en cada partición de los nodos en dos partes, como máximo, la fracción Y de los enlaces es entre diferentes partes, suponiendo que Y / X = 0.95. ¿Por qué habrás terminado? Porque si pudiera aproximar la fracción máxima de enlaces entre dos partes dentro de 0.95, podría distinguir entre los dos casos. El problema distintivo a menudo se llama un problema de brecha debido a la brecha entre las fracciones X e Y.
A continuación, desea mostrar que el problema de la brecha es tan difícil como probar si existe una prueba de tamaño n para una declaración matemática dada, ya que esto demostraría que el corte máximo aproximado de 0.95 es NP-difícil. Esto se realiza mediante una reducción: mostrar una manera eficiente de traducir el problema de prueba al problema de brecha de modo que un algoritmo eficiente para el problema de brecha implica un algoritmo eficiente para el problema de prueba, lo que a su vez significa que el problema de brecha está en menos difícil como el problema de prueba. Concretamente, traduce una declaración matemática y el problema “¿hay una prueba de tamaño como máximo n para la declaración matemática, o cada prueba requiere un tamaño mayor que n?” En una red y el problema “¿hay alguna manera de dividir los nodos de la red en dos partes de tal manera que la fracción de enlaces entre las diferentes partes es al menos X, o ¿la mejor partición tiene como máximo una fracción Y de los enlaces? ”.
Suponiendo que su reducción es correcta, entonces una prueba correcta de tamaño n para la declaración matemática se traduce en una partición de los nodos en la red que tiene al menos una fracción X de los enlaces entre las dos partes. El nuevo formato de la prueba es una asignación de cada uno de los nodos a “parte 1” o “parte 2”. Interesantemente, para verificar la nueva prueba, es suficiente elegir un enlace aleatorio y verificar si sus puntos finales están en diferentes partes (es decir, si el primer punto final está en una parte implica que el segundo punto final está en la otra parte). Una prueba correcta garantiza que la probabilidad de implicación correcta es al menos X, mientras que una prueba incorrecta garantiza que la probabilidad de implicación es como máximo Y. En general, la reducción de “¿hay una prueba de tamaño n?” Al problema de brecha es esencialmente equivalente a una transformación de una prueba a un formato comprobable probabilísticamente. En otras palabras, es un teorema de PCP.
Este teorema de PCP es ligeramente diferente del teorema de PCP que describimos antes: X, la probabilidad de rechazar una prueba correcta, no es 1. Además, aunque la probabilidad Y de aceptar una prueba para una declaración incorrecta es menor que X, puede que no ser mucho más bajo que X. Estos son artefactos de verificar una prueba usando “Max-Cut tests”. Si cambiamos el tipo de pruebas que permitimos, hay métodos para obtener la probabilidad de rechazar una prueba correcta a 0, y la probabilidad de aceptar una prueba para una declaración incorrecta cercana a 0.
Ahora piense en toda la historia si la mecánica cuántica está en la silla.
