La reducción para la aceptación es trivial: si elimina cualquier borde de un ciclo de Hamilton, es una ruta de Hamilton. Por lo tanto, si UHAMCYCLE acepta, también debe hacerlo UHAMPATH. La reducción para el rechazo consiste en, para cada par de vértices sin borde entre ellos, agregar el borde y llamar a UHAMCYCLE. Si ninguna de estas pruebas tiene éxito, el gráfico no tiene ruta de Hamilton, rechazar. El número de tales pares de vértices es polinomial en el número de nodos, por lo que esta es una reducción de tiempo polinomial.
La reducción en la otra dirección es básicamente exactamente lo contrario. Para aceptar: si encuentra una ruta de Hamilton en un gráfico cuando ha eliminado todos los bordes entre dos nodos específicos, al agregar uno de esos bordes nuevamente, puede transformarlo en un ciclo. Puede que tenga que ejecutar su oráculo de búsqueda de ruta una vez por cada par de nodos que tengan un borde entre ellos, pero esto sigue siendo polinómico en la cantidad de nodos. (Este proceso es necesario porque un gráfico con una ruta de Hamilton no contiene necesariamente un ciclo de Hamilton). Para rechazar: Rechazar si el gráfico no contiene una ruta de Hamilton.
- ¿Es posible simular / emular / codificar el poder de pensamiento de una CPU en una GPU?
- ¿Qué es el diseño paramétrico y cuáles son algunos ejemplos de él?
- ¿Aprender la construcción del compilador mejora la habilidad / visión de resolución de problemas de programación? ¿Si es así, cómo? ¿O por qué no?
- ¿Cómo funciona el algoritmo de vista en Quora?
- ¿Alguien podría dar una explicación detallada del algoritmo de Lee para encontrar contornos cercanos en una región?
