Coloquio del IMUNAM - C. U. febrero 2024

Es común implementar algoritmos que resuelven problemas de decisión, es decir, problemas que responden una pregunta cuya respuesta es sí o no.   Por ejemplo, es fácil implementar un algoritmo que reciba como entrada dos enteros positivos, y determine si éstos son primo relativos. Dicho algoritmo podría simplemente responder "sí" o "no", dada una entrada $(x,y)$, sin embargo, si tuviéramos dudas sobre la correcta implementación del algoritmo, no tendríamos información adicional para determinar si la respuesta es correcta o no, lo que nos orillaría a ejecutar un segundo algoritmo que resuelva el mismo problema para "verificar" la respuesta.

Si adicionalmente a la respuesta "sí", el algoritmo devolviera los coeficientes de una combinación lineal de $x$ y $y$ igual a $1$, y adicionalmente a la respuesta "no", el algoritmo devolviera un divisor común de $x$ y $y$ mayor a $1$, entonces sería fácil verificar si una respuesta del algoritmo es correcta, sin necesidad de ejecutar otro algoritmo que resuelva el mismo problema. A esta información adicional que nos ayuda a verificar la correcta implementación de un algoritmo se le llama "certificado", y un algoritmo que devuelve certificados para ambos tipos de respuesta (sí o no), se le conoce como certificador.

En teoría de gráficas, usualmente se buscan algoritmos para determinar si una gráfica tiene o no alguna propiedad.   Es deseable que dichos algoritmos sean certificadores, pero no siempre resulta claro qué debe usarse como certificado.   En esta plática presentaremos caracterizaciones para algunas propiedades de gráficas que dan lugar a certificados naturales que pueden ser utilzados en algoritmos para su reconocimiento.   En muchos casos, la naturaleza constructiva de las demostraciones induce de forma natural un algoritmo certificador que resulta eficiente y fácil de implementar.