cristianmvv escribió en 27 Abr 2019, 22:15:Personalmente opino que es feo mantenerlo vivo asi, hasta que se caigan los servidores y no con un final digno... pero la verdad es que es jodido darle un final digno ya. Bue, tu veras que eres el que tiene el dedo terminador
Los servidores están bajo mantenimiento obligatorio y no te preocupes, cada 2 x 3 están haciendo backups para asegurar que la información no se eche a perder cumpliendo todos los estándares de seguridad.
geballo escribió en 27 Abr 2019, 22:19:Me lo puedes clarificar por favor?
El problema de isomorfismo tiene cono entrada 2 grafos mientras que clique tiene como entrada 1 grafo y un entero k. Como tengo que modificar el input te el primero para pasarlo por el segundo?
No debo también demostrar que puedo validar el certificado de isomorfismo en tiempo polinomico?
Se puede demostrar mediante la reducción de este problema al Problema de la clique, como ya he posteado antes, que lo he consultado y me indica lo siguiente:- Sea
n el número de aristas de
G, se puede ejecutar el problema de isomorfismo de subgrafos
n-2 veces (siendo
G1 una clique de tamaño
3 a n, y G2 siendo G) para encontrar el clique más grande en G.
En este caso si es NP-Completo, la jerarquía polinomial colapsa. Prefiero que lo consultes porque la verdad no puedo especificar exactamente, no tengo la suficiente teoría que yo recuerde, llegué a este tipo de tema y no tengo la suficiente información para poder ayudarte, lo siento, mejor que vayas a Wikipedia u otros portales que al igual encontrarás datos adicionales.