É intuitivo ver que encontrar um caminho hamiltoniano não está em P enquanto encontrar um caminho de Euler?

Eu não tenho certeza de vê-lo. Pelo que entendi, arestas e vértices são complementos um para o outro e é bastante surpreendente que essa diferença exista.

Existe uma maneira boa / rápida / fácil de ver que, na verdade, encontrar um caminho hamiltoniano deve ser muito mais difícil do que encontrar um caminho de Euler?

Talvez a seguinte perspectiva ajude:

Quando você está tentando construir um caminho euleriano, pode prosseguir quase avidamente. Você apenas começa o caminho em algum lugar e tenta andar o maior tempo possível. Se você detectar um círculo, excluirá suas arestas (mas registre que esse círculo foi construído). Com isso, você decompõe o gráfico em círculos, que podem ser facilmente combinados em um tour euleriano. O ponto é que nenhuma de sua decisão "como percorrer o gráfico" pode realmente estar errada. Você sempre terá sucesso e nunca ficará preso.

A situação com os caminhos hamiltonianos é diferente. Novamente, convém construir um caminho caminhando pelas bordas do gráfico. Mas desta vez você pode realmente tomar más decisões. Isso significa que você não pode continuar o caminho, mas nem todos os vértices foram visitados. O que você pode fazer é voltar atrás. Isso significa que você reverte algumas de suas decisões antigas e continua por um caminho diferente. Essencialmente, todos os algoritmos conhecidos pelo problema geral dependem de uma maneira ou de outra do rastreamento de retorno ou da tentativa de um grande conjunto de soluções. Isso, no entanto, é característico para problemas de NP-completo.

Conclusão (simplificada): o caminho euleriano não requer rastreamento, mas o caminho hamiltoniano.

(Observe que pode ser que P = NP e, neste caso, um algoritmo de caminho hamiltoniano inteligente existisse.)

Outro detalhe que pode ajudar sua intuição é que existe um ciclo de Euler se e somente se cada vértice tiver grau uniforme. Um teorema semelhante existe para os caminhos de Euler. Isso decorre de uma prova bastante direta - basicamente, toda vez que você visita um vértice, deve deixá-lo, para que cada "visita" consiga duas do grau do vértice. Isso não explica por que o caminho hamiltoniano é difícil (o que, é claro, nós nem sabemos), mas ajuda a explicar por que é fácil encontrar um caminho de Euler.

Victor Adamchik dá uma boa explicação para a prova. A maioria dos livros de teoria dos grafos / matemática discreta provavelmente também terá uma prova que você pode achar mais fácil.

As outras respostas dão uma boa intuição de por que uma prova tão simples parece não funcionar para os ciclos de Hamilton.

"É intuitivo ver que encontrar um caminho hamiltoniano não está em P enquanto encontrar um caminho de Euler?"

As suposições em sua pergunta não estão corretas.

Note que não sabemos isso$\mathrm{HamPath}$ não está em $\mathsf{P}$! Alguém algum dia poderá encontrar uma caracterização muito inteligente de$\mathrm{HamPath}$ (semelhante à caracterização de $\mathrm{EulerPath}$ como tendo graus pares), o que o colocaria dentro $\mathsf{P}$.

A maioria das pessoas acredita que não está presente$\mathsf{P}$mas não está provado. Os argumentos (e não a prova!) De por que é improvável que isso aconteça$\mathsf{P}$ é o mesmo que os argumentos para $\mathsf{P} \neq \mathsf{NP}$ e a maioria deles não fala muito sobre $\mathrm{HamPath}$ em si, além do fato de que é $\mathsf{NP\text{-}complete}$.

Agora, você pode perguntar por que $\mathrm{HamPath}$ é $\mathsf{NP\text{-}complete}$ mas não podemos mostrar isso $\mathsf{EulerPath}$ é $\mathsf{NP\text{-}complete}$? Porque alguém encontrou uma caracterização dele que está em$\mathsf{P}$ e, em seguida, a resposta seria semelhante à razão pela qual acreditamos que $\mathsf{P} \neq \mathsf{NP}$ portanto, é improvável (mas não provado!) que $\mathsf{EulerPath}$ é $\mathsf{NP\text{-}complete}$.

Aqui está uma maneira rápida de ver isso. O problema HAM-PATH é$\mathsf{NP}$-complete, então atualmente não o fazemos se puder ser resolvido em tempo polinomial ou não. Pelo menos ninguém criou esse algoritmo. O problema do caminho euleriano, por outro lado, é comprovadamente$\mathsf{P}$já que temos algoritmos de tempo polinomial para isso. A$\mathsf{NP}$problemas incompletos, como o HAM-PATH, resistiram a ataques até agora, então essa é uma maneira imediata de ver ou acreditar que é mais difícil do que um problema em $\mathsf{P}$, digamos, encontrar um caminho euleriano.