Reducciones del libro.

22

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.n

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!

Neeldhara
fuente
1
Wiki de la comunidad.
Dave Clarke
@supercooldave: Gracias, supongo que debería haberlo hecho mientras publicaba. Mi descuido!
Neeldhara
@ Jukka: ¡Gracias! Pensé que eso era lo que hizo la edición de supercooldave. Ahora me doy cuenta de que editar agregó una etiqueta. Ahora es un CW :)
Neeldhara
8
Quizás el póster debería aclarar qué se entiende por "del libro". Hubiera pensado que (en analogía con las pruebas del libro) los algoritmos del libro son todos cortos, simples de enunciar, elegantes y funcionan casi mágicamente. Sin embargo, el otro hilo tiene muchas publicaciones con algoritmos increíblemente complejos que no satisfacen ninguna de las propiedades que mencioné.
Robin Kothari
3
@Robin: las percepciones difieren. No encontré ninguna de las pruebas de "Pruebas del LIBRO" simple (bueno, casi ninguna). Y ya la segunda prueba (postulado de Bertrand) requiere varias páginas, por lo que tampoco son cortas. - Por el contrario, encuentro muchos de los algoritmos en el hilo relacionado bastante simple (en retrospectiva, obviamente), y no se puede negar que son cortos.
Konrad Rudolph el

Respuestas:

9

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.

Noam
fuente
Puede encontrar una explicación de esta reducción (si no me equivoco) en la página 7 de "Seguridad comprobable de criptosistemas: una encuesta". Aquí hay un enlace: cs.yale.edu/publications/techreports/tr288.pdf
Neeldhara
9

En el aprendizaje automático, hay muchas reducciones interesantes. Aquí hay unos ejemplos:

  • clasificación multiclase a clasificación binaria ( enlace ): se puede resolver un problema de elegir entre muchas clases resolviendo problemas más fáciles de elegir entre dos.
  • aprendizaje fuerte a aprendizaje débil ( impulso ): se pueden lograr tasas de error arbitrariamente bajas dada la capacidad de lograr un poco mejor que al azar.
  • clasificación a clasificación ( enlace )
  • Pérdida cuadrática de clasificación ( sondeo ): se pueden estimar las probabilidades de pertenencia a la clase mediante el uso de un clasificador con una tasa de error pequeña.

Un tutorial de Alina Beygelzimer, John Langford y Bianca Zadrozny cubre algunos otros.

Lev Reyzin
fuente
2
¡Gracias! Esto parece muy prometedor, y también completamente nuevo para mí. Debería pasar algún tiempo en ese tutorial y las otras referencias también.
Neeldhara
8

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 .

Rui Ferreira
fuente
8

¡Multiplicación entera para transformadas rápidas de Fourier!

Jeffε
fuente
66
y el corolario: ¡cadena que coincide con los FFT!
Suresh Venkat
6

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.

Michaël Cadilhac
fuente
1
La generalización de Rice-Shapiro es aún más hermosa. Vea la exposición de Cutland: books.google.com/… )
Diego de Estrada
3

SAT a 3SAT

kk>3

Rui Ferreira
fuente
3

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 .

Rui Ferreira
fuente
1
La reducción usando NAESAT en lugar de 3SAT (en el libro de Papadimitriou) es más directa.
Diego de Estrada
3

En el sentido de decir, oh, eso fue simple, en retrospectiva:

reduciendo la clasificación a un problema de casco convexo.

usuario200
fuente
2

CUBIERTA EXACTA POR 3-SETS PARA SUBSETAR SUMA

U={1,2,...,3metro}S1,...,SnorteUmetroU

w1,...,wnorteKK

Syo{0 0,1}3metronorte+1Syowyo=jSyo(norte+1)3metro-jK=j=0 03metro-1(norte+1)j

(Mi fuente fue el libro de Papadimitriou).

Diego de Estrada
fuente