¿Es intuitivo ver que encontrar un camino hamiltoniano no está en P mientras que encontrar el camino de Euler sí?

No estoy seguro de verlo. Por lo que entiendo, los bordes y los vértices son complementos entre sí y es bastante sorprendente que exista esta diferencia.

¿Hay una manera buena / rápida / fácil de ver que, de hecho, encontrar un camino hamiltoniano debería ser mucho más difícil que encontrar un camino de Euler?

Quizás la siguiente perspectiva ayude:

Cuando intentas construir un camino euleriano, puedes proceder casi con avidez. Simplemente comienza el camino en algún lugar y trata de caminar el mayor tiempo posible. Si detecta un círculo, eliminará sus bordes (pero registre que este círculo fue construido). Con esto, descompones el gráfico en círculos, que se pueden combinar fácilmente en un recorrido euleriano. El punto es que ninguna de sus decisiones "cómo atravesar el gráfico" puede estar realmente equivocada. Siempre tendrá éxito y nunca se atascará.

La situación con los caminos hamiltonianos es diferente. Nuevamente, es posible que desee construir un camino caminando a lo largo de los bordes del gráfico. Pero esta vez realmente puedes tomar malas decisiones. Esto significa que no puede continuar el camino, pero no se han visitado todos los vértices. Lo que puedes hacer es retroceder. Eso significa que revierte algunas de tus decisiones anteriores y continúa por un camino diferente. Esencialmente, todos los algoritmos que se conocen para el problema general se basan de alguna manera u otra en el seguimiento hacia atrás o en probar un gran conjunto de soluciones. Esto, sin embargo, es característico de los problemas de NP completo.

En resumen (simplificado), la línea de fondo: la ruta de Eulerian no requiere seguimiento posterior, pero la ruta de Hamilton sí.

(Tenga en cuenta que podría ser que P = NP y, en este caso , existiría un inteligente algoritmo de ruta hamiltoniana).

Otro detalle que puede ayudar a su intuición es que existe un ciclo de Euler si y solo si cada vértice tiene un grado par. Un teorema similar existe para los caminos de Euler. Esto se desprende de una prueba bastante directa: básicamente, cada vez que visita un vértice, debe abandonarlo, por lo que cada "visita" toma dos del grado del vértice. Esto no explica por qué el camino hamiltoniano es difícil (que, por supuesto, ni siquiera lo sabemos), pero ayuda a explicar por qué es fácil encontrar un camino de Euler.

Victor Adamchik da una buena explicación de la prueba. La mayoría de los libros de teoría de grafos / matemática discreta probablemente también tendrán una prueba que puede resultarle más fácil.

Las otras respuestas dan una buena intuición de por qué una prueba tan simple no parece funcionar para los ciclos de Hamilton.

"¿Es intuitivo ver que encontrar un camino hamiltoniano no está en P mientras se encuentra el camino de Euler?"

Los supuestos en su pregunta no son correctos.

Tenga en cuenta que no sabemos eso$\mathrm{HamPath}$ no está dentro $\mathsf{P}$! Alguien algún día podría encontrar una caracterización muy inteligente de$\mathrm{HamPath}$ (similar a la caracterización de $\mathrm{EulerPath}$ como tener grados pares) que lo pondrían dentro $\mathsf{P}$.

La mayoría de la gente cree que no está en$\mathsf{P}$Pero no está probado. Los argumentos (¡no prueba!) De por qué es poco probable que esté en$\mathsf{P}$ es lo mismo que los argumentos para $\mathsf{P} \neq \mathsf{NP}$ y la mayoría de ellos no dicen mucho sobre $\mathrm{HamPath}$ en sí aparte del hecho de que es $\mathsf{NP\text{-}complete}$.

Ahora, puedes preguntar por qué $\mathrm{HamPath}$ es $\mathsf{NP\text{-}complete}$ pero no podemos mostrar eso $\mathsf{EulerPath}$ es $\mathsf{NP\text{-}complete}$? Porque alguien ha encontrado una caracterización de eso que está en$\mathsf{P}$ y luego la respuesta sería similar a por qué creemos que $\mathsf{P} \neq \mathsf{NP}$ así que es poco probable (¡pero no probado!) que $\mathsf{EulerPath}$ es $\mathsf{NP\text{-}complete}$.

Aquí hay una forma rápida de verlo. El problema de HAM-PATH es$\mathsf{NP}$-completo, por lo que actualmente no lo hacemos si se puede resolver en tiempo polinómico o no. Al menos a nadie se le ocurrió tal algoritmo. El problema del camino euleriano, por otro lado, es demostrable en$\mathsf{P}$ya que tenemos algoritmos de tiempo polinomiales para ello. Un$\mathsf{NP}$-completo problema como HAM-PATH ha resistido los ataques hasta ahora, por lo que esta es una forma inmediata de ver o creer que es más difícil que un problema en $\mathsf{P}$, digamos encontrar un camino euleriano.