Esto está en la línea de " Algoritmos del libro ". Aunque las reducciones también son algoritmos, pensé que era dudoso pensar en una reducción en respuesta a la pregunta sobre los algoritmos del libro. Por lo tanto, una consulta por separado!
Las reducciones de todo tipo son bienvenidas.
Comenzaré con la reducción realmente simple de la cubierta del vértice al multicut en estrellas. La reducción casi se sugiere una vez que se identifica el problema fuente (antes de lo cual me resultaría difícil creer que el problema sería difícil para las estrellas). Esta reducción implica construir una estrella con hojas y asociar un par de terminales con cada borde del gráfico, y es "fácil de ver" que funciona. Actualizaré esto con un enlace a una referencia, una vez que encuentre uno.
Aquellos a quienes les falta el contexto del libro pueden querer ver la pregunta sobre Algoritmos del libro .
Actualización: me doy cuenta de que no estaba del todo claro en cuanto a lo que califica como una reducción del libro. Encuentro este problema un poco complicado, por lo que confieso haber esquivado el problema a medias, deslizando una referencia al otro hilo :)
Permítanme describir lo que tenía en mente, y supongo que no hace falta decir: YMMV a este respecto. Tengo la intención de hacer una analogía directa con la intención original de las Pruebas del Libro. He visto reducciones que son terriblemente inteligentes, y me dejan con la boca abierta sobre cómo esa secuencia de pensamientos podría haber ocurrido a cualquiera. Si bien tales reducciones me dejan con un sentido definido de asombro, esos no son los ejemplos que estoy buscando recopilar en este contexto.
Lo que estoy buscando son reducciones que se describen sin demasiada dificultad, y tal vez sean ligeramente sorprendentes, por la razón de que son fáciles de entender pero no son fáciles de encontrar. Si estima que la reducción en cuestión requerirá una conferencia para cubrir, entonces es probable que no se ajuste a la factura, aunque estoy seguro de que podría haber excepciones en las que la idea de alto nivel es elegante y el diablo en los detalles (para el registro, no estoy seguro de poder pensar en ninguno).
El ejemplo que di fue deliberadamente simple, y espero que sea un poco, si no perfectamente, ilustrativo de estas características. La primera vez que escuché sobre el corte múltiple fue en un aula, y nuestro instructor comenzó diciendo que no solo es NP-duro en general, es NP-duro incluso cuando está restringido a árboles ... {pausa dramática} de altura uno . Recuerdo que no pude demostrarlo de inmediato, aunque parece obvio en retrospectiva.
Supongo que obvio en retrospectiva describe de cerca lo que estoy buscando. No estoy seguro de si esto tiene algo que ver con la complejidad de la descripción, tal vez hay situaciones en las que algo aparentemente turbio podría clasificarse como elegante, no dude en presentar sus ejemplos (¿excepciones?), Pero realmente agradecería una justificación. Dado que después de algún punto esto es cuestión de gustos, sin duda deberías sentirte libre de encontrar lo que veo como increíblemente complejo, perfectamente hermoso. ¡Espero ver una variedad de ejemplos!
fuente
Respuestas:
Rabin muestra la unidireccionalidad de (x ^ 2 mod N = pq) sin la factorización de N mediante una reducción que muestra que si puede tomar el módulo de raíces cuadradas N = pq, entonces puede factorizar N.
fuente
En el aprendizaje automático, hay muchas reducciones interesantes. Aquí hay unos ejemplos:
Un tutorial de Alina Beygelzimer, John Langford y Bianca Zadrozny cubre algunos otros.
fuente
Teorema de Cook-Levin
Cualquier problema en NP puede reducirse en polytime mediante una máquina de turing determinista a SAT. Para referencia ver 1 .
fuente
¡Multiplicación entera para transformadas rápidas de Fourier!
fuente
Teorema de Rice
Uno de mis favoritos. Reduce el problema de detención a cualquier conjunto de índices (o es un complemento). Ver, por ejemplo, Sipser, problema 5.28.
fuente
SAT a 3SAT
fuente
3SAT a 3COL
Uso de gadgets para reducir 3SAT al problema de decidir si un gráfico es coloreable con 3 colores. Para referencia ver 1 .
fuente
En el sentido de decir, oh, eso fue simple, en retrospectiva:
reduciendo la clasificación a un problema de casco convexo.
fuente
CUBIERTA EXACTA POR 3-SETS PARA SUBSETAR SUMA
(Mi fuente fue el libro de Papadimitriou).
fuente