Problemas que se sienten exponenciales pero son P

12

Estoy tratando de construir una lista de algoritmos / problemas que son "excepcionalmente útiles", como resolver problemas que 'parecen' muy exponenciales en la naturaleza, pero que tienen un algoritmo particularmente inteligente que finalmente los resuelve. Ejemplos de lo que quiero decir:

  • Programación lineal (El algoritmo simplex es tiempo exponencial; ¡llevó mucho tiempo encontrar una solución de tiempo polinomial!)
  • Más en general, la programación semidefinida
  • Prueba de primalidad
  • 2-SAT y HORNSAT
  • Calcular determinantes (si esto no suena difícil, considere el permanente)
  • Encontrar combinaciones perfectas
  • Una variedad de problemas teóricos de grupos difíciles que se pueden lograr utilizando la Clasificación de grupos simples finitos
  • Una variedad de problemas de gráficos duros que se pueden lograr usando caracterizaciones menores prohibidas (incrustación en una superficie arbitraria; delimitación del ancho de árbol y ancho de rama; gráficos reducibles Delta-Wye)
  • Calcular exponenciales en un grupo acotado (es decir, calcular abmodk en logb pasos, como se logra mediante la cuadratura repetida)
  • Cálculos basados ​​en el algoritmo LLL. (Como un caso especial: algoritmo euclidiano. Como un caso más general: algoritmos PSLQ o HJLS).
  • Problemas de restricción sin términos de Taylor (?). Admito que no entiendo completamente esto, pero parece que probablemente subsume los casos 2-SAT / HORNSAT anteriores y cualquier álgebra lineal sobre campos finitos. Ver aquí para una publicación más larga
  • Problemas computables a través de reducciones holográficas .

Como mención honorífica, también mencionaría el isomorfismo gráfico, porque todavía es muy fácil ( ), y es equivalente a muchos otros problemas de isomorfismo:nlog2n

  • Dígrafos / multigrafos / hipergrafías (una especie de problema 'más difícil')
  • Autómatas finitos / CFG

Obviamente, hay una variedad de dificultades en estos, pero todos dejan al menos a algunas personas con un cierto sentido de "sorpresa" en el sentido de que el problema puede sonar difícil pero resultar tratable. El LP puede parecer relativamente sencillo, pero a las personas les llevó bastante tiempo construir una solución real. La cuadratura repetida o la resolución de 2-SAT es algo que un estudiante universitario podría inventar por sí mismo, pero si solo hubiera aprendido sobre los problemas NP-Complete sin haber visto HORNSAT, podría sonar como un candidato natural para NP-Completeness. Resolver el CFSG o tener una forma polinómica para verificar la reducibilidad de Delta-Wye no es tarea fácil.

Espero que esto tenga sentido; obviamente hay muchos atributos subjetivos aquí, pero tengo curiosidad por escuchar lo que otras personas encuentran como soluciones eficientes para problemas "obviamente difíciles".

Alex Meiburg
fuente
Como motivación para esta pregunta (porque un amigo también preguntaba): a menudo hablamos sobre la importancia de enseñar a los estudiantes sobre NP-Completitud e Indecidibilidad, porque les ayuda a reconocer cuándo los problemas serán demasiado difíciles y deberían evitarlos. Esta lista sería "problemas que podría confundir con NP-Complete pero que realmente puede resolver". No es que espere que muchos estudiantes se llenen bajo la impresión de que los determinantes no se pueden calcular, ya que probablemente no se encontrarán con 3SAT en la naturaleza, pero deberían reconocer otros problemas equivalentes
Alex Meiburg,
1
Sospecho que esto es demasiado amplio para que se ajuste bien a nuestro sitio. Pedir una lista exhaustiva de algo no parece el tipo de pregunta que funciona bien aquí. "Tengo curiosidad por escuchar lo que otras personas encuentran ..." suena como el tipo de pregunta que no es adecuada aquí; Vea nuestro centro de ayuda .
DW
1
Entiendo, estaba tratando de reconocer la subjetividad en esta pregunta, pero creo que esta pregunta es en gran medida algo en lo que la gente estaría de acuerdo y aprendería con una discusión productiva. Para preguntas que tengan el tono al que me dirijo, tal vez (aunque conozco un sitio diferente), consulte cstheory.stackexchange.com/questions/20930/… o cstheory.stackexchange.com/questions/11119/… ?
Alex Meiburg
Además, no está nada claro qué "se siente" exponencial para quién.
Raphael

Respuestas:

2

Para mí, uno de los algoritmos más eficientes es el algoritmo Blossom V que encuentra la coincidencia perfecta de peso máximo en un gráfico general:

https://en.m.wikipedia.org/wiki/Blossom_algorithm

Dmitry Kamenetsky
fuente
1
¡Es un buen ejemplo! Sin haberlo pensado o necesitado realmente, creo que tenía la impresión de que la coincidencia máxima en gráficos arbitrarios era NP-difícil. :)
Alex Meiburg
1

Para mí, todos los algoritmos clásicos y más recientes y más eficientes para verificar o encontrar un árbol de expansión mínimo (MST) de un gráfico ponderado de borde conectado son buenos candidatos. Muchos de estos algoritmos se enumeran en wikipedia .

A primera vista, este problema se parece al problema del vendedor ambulante, uno de los pocos problemas NP-hard más famosos. ¡Lo más sorprendente es que existen algoritmos lineales para verificar un MST y muchos algoritmos casi lineales para encontrar un MST! De hecho, uno de los problemas abiertos más famosos en algoritmos es si existe un algoritmo lineal determinista para encontrar un MST en gráficos generales. Resulta que hay estructuras y propiedades matemáticas y gráficas ricas, así como una multitud de aplicaciones prácticas asociadas con MST, lo que lo convierte en uno de los temas más divertidos y ampliables en el curso de informática. Para una introducción exhaustiva un poco desactualizada pero muy bien escrita, consulte el tutorial de Jason Eisner .

John L.
fuente