Me interesan las pruebas de afirmaciones de la forma "Objetos finitos $A$ y $B$ son isomorfos" que no son constructivos, en el sentido de que la prueba no exhibe el isomorfismo real en cuestión.
Un requisito más fuerte (y especificado con mayor precisión) sería un caso en el que es computacionalmente fácil escribir una prueba, pero computacionalmente difícil extraer el isomorfismo dada la prueba, por ejemplo, una clase de grafos para los que uno puede generar fácilmente triples $(G,H,P)$ con $P$ una prueba de que $G$ y $H$ son isomorfas pero para las que no hay un algoritmo (conocido) eficiente para tomar en $(G,H,P)$ y devuelve una permutación de los vértices que presentan el isomorfismo.
Algunos ejemplos de cosas que encajarían, si existieran:
-
(dar una prueba no constructiva de que) todos los objetos de tipo $X$ se especifican de forma única por sus valores en cinco medidas específicas; observe que $A$ y $B$ alinearse en todas esas medidas.
-
La función fácil de calcular de los gráficos $f(G,H)$ resulta ser igual al producto, sobre todas las reetiquetas de $G$ del número de aristas en las diferencias simétricas entre los conjuntos de aristas de $H$ y la copia reetiquetada de $G$ . (Esto ocurre por alguna bonita cancelación algebraica o algo así, como la forma de calcular los determinantes en el tiempo $O(n^3)$ .) Ahora observamos que $f(G,H) = 0$ a través del cálculo directo, y concluyen que un reetiquetado sin ninguna diferencia con $H$ debe existir.
-
Grupos $G$ y $H$ de orden $n$ especificados por sus tablas de multiplicación, puede demostrarse fácilmente que se incrustan como subgrupos de un grupo mayor $K$ que podemos clasificar y demostrar más fácilmente las cosas. Pero la existencia de dos subgrupos no isomorfos de orden $n$ en $K$ implicaría algo sobre sus subgrupos Sylow que sabemos que es falso.
¿Hay buenos ejemplos de este fenómeno? ¿Razones para pensar que no ocurre? También me interesaría que me indicaran la bibliografía sobre temas relacionados.
