Este artículo explora el uso de la tecnología de IA para descubrir nuevas estructuras combinatorias que mejoran las limitaciones existentes de los algoritmos eficientes. Específicamente, utilizamos AlphaEvolve (un agente de codificación LLM) para estudiar la dureza promedio de los casos para MAX-CUT y los Conjuntos MAX-Independientes, así como la dureza aproximada del peor caso para MAX-k-CUT. De esta manera, mejoramos los límites superior e inferior del algoritmo de autenticación para MAX-CUT y los Conjuntos MAX-Independientes, y obtenemos nuevos resultados de probabilidad no aproximada para MAX-4-CUT y MAX-3-CUT. Además, proponemos un método para mejorar eficientemente el proceso de verificación utilizando AlphaEvolve.