Problemas algorítmicos difíciles de ver facilitados por teoremas

28

Estoy buscando buenos ejemplos, donde ocurre el siguiente fenómeno: (1) Un problema algorítmico parece difícil, si desea resolverlo trabajando desde las definiciones y utilizando solo resultados estándar. (2) Por otro lado, se vuelve fácil, si conoce algunos teoremas (no tan estándar).

El objetivo de esto es ilustrar para los estudiantes que aprender más teoremas puede ser útil, incluso para aquellos que están fuera del campo de la teoría (como ingenieros de software, ingenieros informáticos, etc.). Aquí hay un ejemplo:

Pregunta: Dados los enteros , ¿existe un gráfico vértice (y si es así, encuentre uno), de modo que su conectividad de vértice sea , su conectividad de borde sea y su grado mínimo sea ?n k l dn,k,l,dnkld

Tenga en cuenta que requerimos que los parámetros sean exactamente iguales a los números dados, no son solo límites. Si desea resolver esto desde cero, puede parecer bastante difícil. Por otro lado, si está familiarizado con el siguiente teorema (ver Teoría de gráficos extremos de B. Bollobas), la situación se vuelve bastante diferente.

Teorema: Sean enteros. Existe un gráfico de -vértices con conectividad de vértice , conectividad de borde y grado mínimo , si y solo si se cumple una de las siguientes condiciones:n k l dn,k,l,dnkld

  • 0kld<n/2 ,
  • 12d+2nkl=d<n1
  • k=l=d=n1.

Estas condiciones son muy fáciles de verificar, ya que son simples desigualdades entre los parámetros de entrada, por lo que la pregunta de existencia se puede responder sin esfuerzo. Además, la prueba del teorema es constructiva, resolviendo también el problema de la construcción. Por otro lado, este resultado no parece lo suficientemente estándar, por lo que puede esperar que todos lo sepan.

¿Puede proporcionar más ejemplos en este espíritu, donde conocer un teorema (no tan estándar) simplifica enormemente una tarea?

Andras Farago
fuente
1
No estoy seguro de entender completamente sus preguntas. El ejemplo que da es un problema no trivial para el cual Bollobas ha dado un algoritmo (que implica una caracterización). Entonces, mi impresión con su ejemplo es que cualquier algoritmo no trivial será una respuesta ...
Bruno
3
Primalidad y el teorema de AKS.
Lamine
@Bruno: Lo que quiero decir es que la tarea algorítmica se vuelve mucho más fácil si conoces un teorema, que no se conoce bien, por lo que es posible que nunca hayas oído hablar de él. El ejemplo presentado no es perfecto en el sentido de que aquí el teorema no solo ayuda, sino que resuelve el problema. Lo que realmente estoy buscando es cuando un teorema ayuda, proporciona un atajo útil, pero no resuelve completamente el problema en sí mismo.
Andras Farago
3
Wiki de la comunidad?
Joshua Grochow
1
Teorema de Robertson-Seymour, también conjeturas que facilitan la determinación de encontrar primos.
Kaveh

Respuestas:

31

Decidir el isomorfismo de grupos simples , dado por sus tablas de multiplicar. El hecho de que esto se pueda hacer en tiempo polinomial se deriva directamente del hecho de que todos los grupos simples finitos pueden ser generados por un máximo de 2 elementos, y actualmente la única prueba conocida de ese hecho utiliza la Clasificación de grupos simples finitos (quizás el teorema más grande - en términos de autores, artículos y páginas, siempre probados).

Joshua Grochow
fuente
3
¡Este es un gran ejemplo! Por cierto, los comentarios a esta respuesta afirman que, en cierto sentido, este teorema es tan difícil como la clasificación: mathoverflow.net/a/59216/35733
Sasho Nikolov
32

Si entiendo su pregunta correctamente, un ejemplo canónico sería decidir si un gráfico tiene un circuito euleriano: equivalente a verificar que G esté conectado y que cada vértice tenga un grado par.GG

Sasho Nikolov
fuente
20

Esta tarde estaba leyendo Stringology, la teoría de cuerdas "real" .

Problema: Si e y son dos cadenas sobre algún alfabeto, cuando hay algunos enteros positivos m , n tal que x m = y n .xym,nxm=yn

Teorema: Hay enteros positivos tales que x m = y n si y solo si x y = y x .m,nxm=ynxy=yx

Pratik Deoghare
fuente
9

Encontrar el número de raíces reales (distintas) de un polinomio real, ya sea en todo ℝ o en un intervalo dado. El teorema de Sturm le dice que una secuencia de polinomios que cumple un pequeño número de requisitos se puede usar para contar el número de raíces reales de un polinomio con coeficientes reales.

Entonces, todo lo que tiene que hacer es construir una secuencia de este tipo (que no es muy difícil, pero requiere algunos casos extremos y manejo del caso de polinomios no separables), y Bob es su tío.

Sorprendentemente, pocas personas conocen este resultado, a pesar de ser bastante antiguo (1829). Se usa en muchos sistemas de álgebra computacional, pero todos los profesores de matemáticas de mi universidad a quienes les pregunté no sabían el Teorema de Sturm o solo lo sabían por su nombre y tenían algo que ver con las raíces de los polinomios.

La mayoría de las personas se sorprenden cuando les dice que algo como contar raíces reales exactamente es tan fácil y no requiere ninguna aproximación, teniendo en cuenta que la búsqueda de las raíces es mucho más difícil. (Recuerde que para polinomios de grado ≥ 5, ni siquiera existe una fórmula "adecuada" para las raíces)

Manuel Eberl
fuente
9

Teorema: cada gráfico plano tiene un vértice con un grado máximo de 5.

Problema: Diseñe una representación de gráficos planos donde podamos verificar si ( u , v ) es una ventaja en el tiempo O ( 1 ) .O(n)(u,v)O(1)

Podemos eliminar el vértice con un grado máximo de 5 y agregarlo a una lista como clave y sus vecinos como valores. El gráfico restante también es plano y tiene un vértice con un grado máximo de 5. Por lo tanto, el espacio consumido es como máximo de . Podemos verificar si u está en la lista de adyacencia de v ; si no, podemos verificar si v está en la lista de adyacencia de u . Esto toma como máximo 10 pasos.5nuvvu10

Pratik Deoghare
fuente
55
Con un poco más de cuidado, puede reducir el tamaño de la lista almacenada en cada vértice a 3 y el número de pasos para verificar la adyacencia a 6. Ver: Orientaciones planas con bajo grado de salida y compactación de matrices de adyacencia. M. Chrobak y D. Eppstein. Theor Comp. Sci. 86 (2): 243–266, 1991. ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
David Eppstein
7

Creo que el posterchild para esta categoría, al menos en lo que respecta a la asimetría de dificultad, es el siguiente problema:

Dado un gráfico plano , ¿es G 4 coloreable?GG

El teorema de cuatro colores simplifica el algoritmo a return true.

Jonas Kölker
fuente
6

Si un polinomio real (multivariado) puede expresarse como una suma de cuadrados de polinomios reales puede resolverse mediante reducción a una programación semi-definida. Necesita saber SDP y ese SDP se puede resolver de manera eficiente.p

Chandra Chekuri
fuente
5

Otro ejemplo: dado un gráfico no dirigido, ¿tiene un corte mínimo en el que todos los bordes son disjuntos? Si es así, encuentra uno.

nn(n1)/2

Se puede extender a cortes casi mínimos, que son más grandes que el corte mínimo, pero como máximo por un factor constante. Su número aún está limitado por un polinomio.

(No busqué una referencia, recuerdo que estos resultados se deben a D. Karger).

Andras Farago
fuente
4

Problema: Satisfacción de una fórmula MSO (lógica monádica de segundo orden) sobre palabras finitas.

Teorema: MSO es equivalente a autómatas finitos sobre palabras finitas.

Lo anterior se puede elevar a palabras infinitas, árboles finitos, árboles infinitos.

Denis
fuente
4

Un ejemplo un poco más complicado: la factorización de matriz no negativa , cuando el rango no negativo es constante.

AMm×nUMm×kVMk×nA=UVA

O(r2)r

(mn)O(r2)UV(mn)o(r)

zotachidil
fuente
4

Decisional Diffie Hellman

(g,ga,gb,gc)gGgc=gab

Bajo los supuestos estándar de dureza del problema de registro discreto, este problema también puede parecer difícil.

e(g,gc)=?e(ga,gb)

e:G×GGT

Puede leer más sobre esto en El decisivo problema del hombre del infierno , Boneh'98 o una búsqueda en Google sobre Emparejamientos

Subhayan
fuente
3

(Trivialmente) la existencia de un equilibrio de Nash en un juego finito, un número par de caminos hamiltonianos en un gráfico cúbico, varios tipos de puntos fijos, comparaciones decentemente equilibradas en órdenes parciales y muchos otros problemas de PPAD.

Yonatan N
fuente
La existencia de Nash Equilibrium, y muchas de las otras pruebas de existencia que caracterizaron al PPAD, no parecen hacer que ninguno de estos problemas sea más fácil de resolver algorítmicamente ...
Joshua Grochow
1
Me refería a la versión de decisión de estos problemas.
Yonatan N
2

((V,E),s,t)EEst(V,E)E

st(V,E)st

Max
fuente
1
Se puede decir que el flujo es fácil si sabes que LP es fácil. Por lo tanto, dos grandes teoremas (LP en tiempo poli y maxflow-mincut) nos permiten calcular cortes mínimos.
Chandra Chekuri
@ChandraChekuri, mi sensación personal es que eso no se ajusta a la pregunta: el teorema de que LP es solucionable en polytime no nos ayuda a construir un algoritmo para cortes mínimos. Necesitamos el algoritmo LP real.
Max
Realmente no. Si puede encontrar el valor de corte mínimo en un gráfico dado de manera eficiente, entonces puede usar dicho algoritmo para encontrar el corte real en sí.
Chandra Chekuri
2

Aquí hay otro ejemplo: dado un gráfico simple no dirigido, decida si tiene dos circuitos separados de vértice.

23

3K5K3,n3

Dado que es fácil verificar si una gráfica es una de las gráficas permitidas por el Teorema, esto nos proporciona un algoritmo de tiempo polinómico para el problema de decisión.

Notas: (1) La demostración del teorema no es nada fácil. (2) Una vez que decidimos que existen dos circuitos disjuntos, parece menos claro cómo resolver el problema de búsqueda asociado , es decir, cómo encontrar realmente dichos circuitos. El teorema no da consejos directos a eso.

Andras Farago
fuente
1

ejemplos menos complejos: hay algunas propiedades de tipo teorema que muestran que los algoritmos codiciosos para algunos problemas son óptimos. no es tan obvio para los no iniciados que un algoritmo codicioso puede encontrar un árbol de expansión mínimo . conceptualmente algo similar es el algoritmo de Dijkstra para encontrar la ruta más corta en un gráfico. en realidad, en ambos casos, los "teoremas" asociados son casi los mismos que los algoritmos.

vzn
fuente
Creo que esta será una mejor respuesta si, por ejemplo, incluye una declaración de la propiedad de corte de MST y menciona cómo implica la corrección de toda una clase de algoritmos codiciosos de MST.
Sasho Nikolov
Propiedad de corte MST listada en la página de Wikipedia. tal vez pueda refirir otras generalizaciones no cubiertas allí. Por cierto, recuerde que el interlocutor solicitó ejemplos que sirvan a "aquellos que están fuera del campo de la teoría" (otros buenos ejemplos dados pueden ser demasiado avanzados para los extraños)
vzn
TeTeABeE(A,B)
1

Encuentra la secuencia de números de Fibonacci que son el producto de otros números de Fibonacci. Por ejemplo, el número 8 de Fibonacci está en la secuencia porque 8 = 2 * 2 * 2, y 2 es un número de Fibonacci que no es igual a 8. El número 144 de Fibonacci está en la secuencia porque 144 = 3 * 3 * 2 * 2 * 2 * 2, y 2 y 3 son números de Fibonacci que no son iguales a 144.

El teorema de Carmichael implica que 8 y 144 son los únicos términos de esta secuencia.

Bob Lyons
fuente