¿Deberían las reducciones hacernos más o menos optimistas para la trazabilidad de un problema?

14

Me parece que la mayoría de los teóricos de la complejidad generalmente creen en la siguiente regla filosófica:

Si no podemos imaginar un algoritmo eficiente para el problema , y podemos reducir el problema Una de problema B , entonces probablemente no es un algoritmo eficiente para el problema B , tampoco.AABB

Esta es la razón por la cual, por ejemplo, cuando se demuestra que NP-Complete tiene un nuevo problema, simplemente lo archivamos como "demasiado difícil" en lugar de entusiasmarnos con un nuevo enfoque (problema ) que finalmente podría mostrar .BP=NP

Estaba discutiendo esto con un compañero de posgrado en otro campo científico. Encontró esta idea muy contradictoria. Su analogía:

Eres un explorador que busca un puente entre los continentes norteamericano y asiático. Durante muchos meses has intentado y no has podido encontrar un puente terrestre desde el área continental de los Estados Unidos hasta Asia. Luego descubres que los Estados Unidos continentales están conectados por tierra con el área de Alaska. Te das cuenta de que un puente terrestre desde Alaska a Asia implicaría un puente terrestre desde el continente de EE. UU. A Asia, que estás bastante seguro de que no existe. Para que no pierdas el tiempo explorando cerca de Alaska; solo vete a casa.

Nuestra regla filosófica anterior suena bastante tonta en este contexto. ¡No podría pensar en una buena refutación! Así que les estoy entregando a ustedes: ¿Por qué deberíamos tratar una reducción como hacer que el problema más difícil en lugar de hacer que el problema sea ​​más fácil?B AABBA

GMB
fuente
2
Por cierto, cada vez que escribimos una subrutina estamos afirmando que hace que A sea más fácil. ABA
Suresh Venkat
1
P / NP son solo las clases de complejidad más "conocidas" y las que se enseñan a los neófitos. es un universo entero que se está mapeando lentamente de "pequeño" a "grande". las reducciones se están preparando en gran medida para el día, aún no aquí, cuando las clases principales pueden discriminarse entre sí con mayor precisión de la que ahora es posible / disponible. Tal vez esta pregunta pueda responderse con otras analogías intuitivas. Una posible analogía científica es que las clases de complejidad son para TCS como lo son las partículas (fundamentales) para la física. Y todavía estamos intentando determinar las interrelaciones. etc ... puede responder más tarde.
vzn
77
@vzn Por favor, no describa a los estudiantes de posgrado como "neófitos": tiene connotaciones bastante negativas. Incluso "principiante" no da suficiente crédito.
David Richerby 01 de
1
Encontré algunos ejemplos, pero creo que hay muchos de ellos, en los que la reducción se usa explícitamente "en la dirección opuesta (positiva)": use un problema de tiempo polinómico para modelar un problema A (es decir, encuentre una reducción A m B ) demostrando de esta manera que A puede resolverse en tiempo polinómico. Recuerdo esto sobre los problemas de planificación: Teorema 3.10 : El problema del mundo de bloques se puede reducir a P L A N S A T + 1BAAmBAPLANSAT1+(que se puede resolver en el tiempo polinómico) en Tom Bylander: La complejidad computacional de la planificación de TIRAS proposicionales. Artif. Intell. 69 (1-2): 165-204 (1994)
Marzio De Biasi
1
Hay un ejemplo interesante con el problema de la camarilla plantada: Frieze y Kannan demostraron que encontrar una camarilla plantada en un gráfico aleatorio puede reducirse a aproximarse al máximo de una forma cúbica, para casos aleatorios. En el documento presentan claramente su resultado como un acercamiento a la camarilla plantada. Hasta donde sé, actualmente esta reducción generalmente se ve como evidencia de la dureza de los problemas en los tensores tridimensionales.
Sasho Nikolov

Respuestas:

14

Creo que esta es una muy buena pregunta. Para responderlo, debemos darnos cuenta de que:

  • no todas las reducciones son iguales,
  • Para sentirnos optimistas, necesitamos aprender algo realmente útil.

Por lo general, cuando descubrimos una reducción no trivial , cae en una de las siguientes categorías:UNsi

  1. Aprendimos algo útil sobre el problema A (y nada sobre el problema B).
  2. Aprendimos algo desalentador sobre el problema B (y nada sobre el problema A).

Un poco más precisamente, estos dos casos se pueden caracterizar de la siguiente manera:

  1. Descubrimos que el problema A tiene una estructura oculta, lo que hace posible diseñar un algoritmo nuevo e inteligente para resolver el problema A. Solo necesitamos saber cómo resolver el problema B.

  2. Nos dimos cuenta de que en algunos casos especiales, el problema B es básicamente el problema A disfrazado. Ahora podemos ver que cualquier algoritmo para resolver el problema B tiene que resolver al menos estos casos especiales correctamente; y resolver estos casos especiales es esencialmente equivalente a resolver el problema A. Volvemos al punto de partida: para avanzar en el problema B, primero debemos avanzar en el problema A.

Las reducciones de tipo 1 son comunes en el contexto de resultados positivos, y estas son ciertamente buenas razones para sentirse optimista.

Sin embargo, si considera las reducciones de dureza que encontramos en el contexto de, por ejemplo, pruebas de dureza NP, casi siempre son del tipo 2.

Tenga en cuenta que incluso si no sabe nada sobre la complejidad computacional del problema A o B, puede saber si su reducción es del tipo 1 o del tipo 2. Por lo tanto, no necesitamos creer, por ejemplo, P ≠ NP para determinar si debemos sentirnos optimistas o pesimistas. Podemos ver lo que hemos aprendido gracias a la reducción.

Jukka Suomela
fuente
PAG=nortePAG
16

Lo que falta en la analogía es alguna noción de las distancias relativas involucradas. Reemplacemos Alaska en nuestra analogía con la luna:

Eres un explorador que busca un puente entre los continentes norteamericano y asiático. Durante muchos meses has intentado y no has podido encontrar un puente terrestre desde el área continental de los Estados Unidos hasta Asia. Luego descubres que la parte continental de los EE. UU. Está conectada por tierra a la luna. Ya está seguro de que la luna está muy lejos de Asia, por lo que ahora puede estar seguro de que América del Norte también está muy lejos de Asia por la desigualdad del triángulo.

Geoffrey Irving
fuente
2
+1. Esta respuesta saca un punto más profundo. Las reducciones pueden "separar las cosas" y "juntarlas". Cuál de ellos parece hacer depende de su creencia previa.
Suresh Venkat
9

No es cierto que siempre veamos los teoremas de reducción como declaraciones de dureza. Por ejemplo, en algoritmos a menudo reducimos un problema a LP y SDP para resolverlos. Estos no se interpretan como resultados de dureza sino resultados algorítmicos. Sin embargo, aunque técnicamente son reducciones, a menudo no nos referimos a ellas como tales. Lo que queremos decir con una reducción es usualmente una reducción a algún problema difícil (NP-).

UNsiUNsisiUNUNUNsisi. La mayoría de los investigadores encuentran que es más probable que P no sea igual a NP, e incluso conjeturan que SAT requiere tiempo exponencial. En otras palabras, se cree que SAT es muy difícil. Si acepta estas conjeturas, es completamente razonable considerar las reducciones que prueban la universalidad de un problema para NP como un problema difícil. (Por qué los investigadores encuentran que P no es igual a NP más probable es un tema diferente, ha habido varias publicaciones en blogs sobre blogs de teoría al respecto).

Parte de la razón por la que reemplazamos el límite inferior con los resultados de universalidad (es decir, hay una reducción de cada problema en una clase al problema) es nuestra falta de éxito en demostrar buenos límites inferiores generales (es consistente con el estado actual del conocimiento ese SAT se puede resolver en tiempo determinista lineal).

Kaveh
fuente
¿A es más fácil que B? La mayoría de las reducciones implican una penalización de tiempo determinada, y es muy posible que una reducción particular sea tan rápida como la solución más rápida para A. Una reducción de A a B muestra que A no es mucho más difícil que B, pero aún podría serlo. Más fuerte.
Brilliand
Más fácil aquí significa hasta la clase de equivalencia de la clase de reducciones.
Kaveh
¿Es posible que dos problemas sean mutuamente más fáciles entre sí? Me generalizo a las clases de equivalencia, pero creo que aún debería ser "al menos tan fácil como".
Brilliand
Más fácil no significa estrictamente más fácil.
Kaveh
3

En realidad, el descubrimiento de Alaska tendría el efecto contrario, al menos al principio. Ya que se extiende al oeste hasta el momento, sería que la gente piensa que, bueno, tal vez no es un puente de tierra, después de todo (el ser analogía, bueno, tal vez P  =  NP ya que esta nueva NP miradas problemas -Complete como un buen candidato para tales teniendo una solución de tiempo polinomial). Sin embargo, una vez que Alaska se haya explorado a fondo y no se haya encontrado ningún puente terrestre, la gente probablemente estaría más convencida que antes de que Asia y América están separadas.

David Richerby
fuente
3

la pregunta introduce una analogía / metáfora particular que no usan mucho los expertos y se enfoca solo en P / NP y no menciona ninguna otra clase de complejidad, mientras que los expertos tienden a verla como un gran universo interconectado de entidades como en el notable diagrama creado por Kuperberg . sería genial compilar una gran lista de analogías de clases de complejidad, hay muchas analogías de este tipo. habla de problemas de "archivado" comprobados como NP completo y "entusiasmo por nuevos enfoques".

se puede entender que hubo un "entusiasmo" inicial al descubrir la clase completa de NP, pero algo de "entusiasmo" se ha desvanecido después de más de cuatro décadas de intenso esfuerzo para demostrar que P ≠ NP no parece haber sido prometedor y algunos investigadores creen que nosotros No están más cerca. La historia está llena de investigadores que pasaron largos años trabajando en problemas sin ningún progreso aparente o mucho, a veces con arrepentimiento posterior. por lo tanto, NP completo puede servir (para tomar prestada la analogía de Aaronson) como una especie de "cerca eléctrica", una advertencia / advertencia de no involucrarse demasiado en los intentos de (aquí literalmente, en más de un sentido) problemas "intratables".

Es cierto que hay un aspecto importante de la "catalogación" de problemas completos de NP que aún continúa. sin embargo, la investigación masiva "de grano fino" sobre problemas clave de NP completos (SAT, detección de camarillas, etc.) continúa. (en realidad, un fenómeno muy similar ocurre con problemas indecidibles de wrt: una vez que se ha demostrado que es indecidible, es como si se dictaminara como "tierra sin mans" para futuras investigaciones).

así que todos los problemas completos de NP son equivalentes en cuanto a la teoría actual y esto a veces se muestra en conjeturas sorprendentes como la conjetura del isomorfismo de Berman-Hartmanis . Los investigadores esperan que esto cambie algún día.

Esta pregunta está etiquetada soft-questioncon una buena razón. no encontrará científicos serios que discutan mucho las analogías en sus documentos, que se centran en la ciencia popular , prefiriendo centrarse en la precisión / rigor matemático (y como se enfatiza en las pautas de comunicación para este grupo). Sin embargo, hay algún valor aquí para educar y comunicarse con extraños / laicos.

Aquí hay algunas "contra-analogías" para los legos junto con "pistas de investigación" a los conceptos. esto podría hacerse en una lista más larga.

  • Hay una analogía de territorios en la pregunta. pero tiene más sentido pensar en las principales regiones de la teoría de la complejidad incluidos dentro de las clases conocidas como terra incognita . en otras palabras, hay una región de P intersecta NP. tanto P como NP se entienden bastante bien, pero no se sabe si la región P ⋂ NP-hard (P intersect NP-hard) está vacía o no.

  • Aaronson recientemente dio la metáfora de dos tipos aparentemente diferentes de especies de ranas que nunca se mezclan para P / NP. También se refirió a la "cerca eléctrica invisible" entre los dos.

  • La física de partículas estudia el modelo estándar. la física estudia la composición de partículas al igual que la teoría de la complejidad estudia la composición de las clases de complejidad. En física, existe cierta incertidumbre acerca de cómo algunas partículas dan lugar a otras ("establecer límites") al igual que en la teoría de la complejidad.

  • "El complejo zoológico" , es como muchos animales exóticos que tienen diferentes capacidades, algunos pequeños / débiles y otros grandes / poderosos.

  • Las clases de complejidad son como un continuo continuo de tiempo / espacio como se ve en los teoremas de la jerarquía de tiempo / espacio con "puntos de transición" clave (sorprendentemente bastante análogos a las transiciones de fase de materia física) entre los diversos estados.

  • una máquina de Turing es una máquina con "partes móviles" y las máquinas hacen un trabajo equivalente a las mediciones de energía , y tienen mediciones de tiempo / espacio . así que las clases de complejidad pueden verse como "energía" asociada con las transformaciones de entrada-salida de caja negra.

  • Hay muchos posibles análogos de la historia de las Matemáticas, es decir, el problema de cuadrar el círculo, encontrar soluciones algebraicas para la ecuación quíntica, etc.

  • Mundos de Impaggliazo

  • El nuevo libro de Fortnows contiene mucha analogía científica popular para la minería.

  • Cifrado / descifrado: Turing trabajó de manera famosa en esto durante la Segunda Guerra Mundial y muchos teoremas que prueban las diferencias en las clases de complejidad pueden parecer análogos a los problemas de descifrado. esto se hace más sólido con documentos como Natural Proofs, donde la separación de clases de complejidad se relaciona directamente con "romper" generadores de números pseudoaleatorios.

  • Compresión / descompresión: diferentes clases de complejidad permiten / representan diferentes cantidades de compresión de datos. por ejemplo, suponga que P / poly contiene NP. eso significaría que hay entidades "más pequeñas" (es decir, circuitos) que pueden "codificar" problemas completos de NP "más grandes", es decir, las estructuras (de datos) más grandes se pueden "comprimir" de manera eficiente en estructuras (de datos) más pequeñas.

  • A lo largo de la analogía zoológico / animal, hay un fuerte aspecto de ciego y elefante en la teoría de la complejidad. el campo todavía está aparentemente / posiblemente en sus primeras etapas de un arco muy largo (esto no es inverosímil o inaudito en otros campos matemáticos que tienen períodos de siglos o incluso milenios) y muchos conocimientos pueden verse como parciales, disjuntos y fragmentado.

En resumen, la pregunta se refiere al "optimismo asociado con las reducciones". Los científicos generalmente se abstienen de las emociones o incluso se ríen de ellas a veces en su búsqueda puramente lógica. existe un equilibrio entre el pesimismo a largo plazo y el optimismo cauteloso en el campo y, si bien hay cierto margen para la informalidad, todos los investigadores serios deben esforzarse por lograr la imparcialidad en sus actitudes profesionales como parte de la descripción del trabajo. comprensiblemente, hay un enfoque en las pequeñas victorias y el incrementalismo y no dejarse llevar ".

vzn
fuente
1
Gracias, esta es una gran respuesta. ¡Qué diagrama tan fantástico de Kuperberg!
GMB
si. Con suerte, eso debería dejar más claro que las reducciones son un mecanismo para asignar problemas (previamente desconocidos) dentro de un "sistema de clasificación maestro" algo así como phylum / especies, etc. en biología. Esto generalmente apoya en lugar de excluir el estudio adicional. también en el diagrama, el continuo de dureza computacional varía de "bajo / fácil" en la parte inferior a "duro" en la parte superior. Lo que es notable es el contraste / dicotomía de los aspectos discretos y continuos de la jerarquía de clases. también, las clases principales / clave como P / NP funcionan algo así como "centros" con muchas otras clases relacionadas con ellos.
vzn