Pruebas de existencia de algoritmos no constructivas

Un ejemplo sencillo de algoritmo no constructivo fue publicado en 1982 por Elwyn R. Berlekamp , ​​John H. Conway y Richard K. Guy en su libro Winning Ways for Your Mathematical Plays . Se trata del juego Sylver Coinage , en el que los jugadores se turnan para especificar un número entero positivo que no puede expresarse como la suma de valores previamente especificados, y un jugador pierde cuando se ve obligado a especificar el número  1. Existe un algoritmo (presentado en el libro como un diagrama de flujo) para determinar si un primer movimiento dado es ganador o perdedor: si es un número primo mayor que tres, o uno de un conjunto finito de números 3-suaves , entonces es un primer movimiento ganador, y de lo contrario es perdedor. Sin embargo, se desconoce el conjunto finito.

Las demostraciones algorítmicas no constructivas para problemas en teoría de grafos fueron estudiadas a partir de 1988 por Michael Fellows y Michael Langston . ^{[ 1 ]}

Una pregunta común en la teoría de grafos es si un grafo de entrada determinado tiene una propiedad específica. Por ejemplo:

Entrada: un grafo G.

Pregunta: ¿Se puede incrustar G en un espacio tridimensional, de manera que no haya dos ciclos disjuntos de G vinculados topológicamente (como en los eslabones de una cadena)?

Existe un algoritmo altamente exponencial que determina si dos ciclos incrustados en un espacio tridimensional están conectados, y se podrían probar todos los pares de ciclos en el grafo, pero no es obvio cómo considerar todas las posibles incrustaciones en un espacio tridimensional. Por lo tanto, a priori no está nada claro si el problema de la conexión es decidible.

Sin embargo, existe una demostración no constructiva que muestra que la vinculación es decidible en tiempo polinomial. La demostración se basa en los siguientes hechos:

• El conjunto de grafos para los que la respuesta es "sí" es cerrado bajo la operación de tomar menores . Es decir, si un grafo G puede incrustarse sin enlaces en el espacio tridimensional, entonces cada menor de G también puede incrustarse sin enlaces.
• Para cualquier par de grafos G y H , es posible encontrar en tiempo polinomial si H es un menor de G.
• Según el teorema de Robertson-Seymour , cualquier conjunto de grafos finitos contiene solo un número finito de elementos mínimos menores. En particular, el conjunto de instancias "sí" tiene un número finito de elementos mínimos menores.

Dado un grafo de entrada G , el siguiente "algoritmo" resuelve el problema anterior:

Para cada elemento mínimo menor H :

Si H es un menor de G , entonces devuelve "sí".

devolver "no".

La parte no constructiva aquí es el teorema de Robertson-Seymour. Si bien garantiza que existe un número finito de elementos mínimos menores, no nos dice cuáles son estos elementos. Por lo tanto, en realidad no podemos ejecutar el "algoritmo" mencionado anteriormente. Sin embargo, sabemos que existe un algoritmo y que su tiempo de ejecución es polinomial.

Existen muchos otros problemas similares cuya decidibilidad puede probarse de manera similar. En algunos casos, el conocimiento de que un problema puede probarse en tiempo polinomial ha llevado a los investigadores a buscar y encontrar un algoritmo real de tiempo polinomial que resuelve el problema de una manera completamente diferente. Esto demuestra que las pruebas no constructivas pueden tener resultados constructivos. ^{[ 1 ]}

La idea principal es que un problema puede resolverse mediante un algoritmo que utiliza, como parámetro, un conjunto desconocido. Aunque el conjunto sea desconocido, sabemos que debe ser finito, por lo que existe un algoritmo de tiempo polinomial.

Existen muchos otros problemas combinatorios que pueden resolverse con una técnica similar. ^{[ 2 ]}