Apakah intuitif untuk melihat bahwa menemukan jalur Hamilton tidak dalam P sementara menemukan jalur Euler?

Saya tidak yakin melihatnya. Dari apa yang saya mengerti, tepi dan simpul saling melengkapi satu sama lain dan cukup mengejutkan bahwa perbedaan ini ada.

Adakah cara yang baik / cepat / mudah untuk melihat bahwa sebenarnya menemukan jalur Hamilton harus jauh lebih sulit daripada menemukan jalur Euler?

Mungkin perspektif berikut membantu:

Saat Anda mencoba untuk membangun jalur Euler, Anda dapat melanjutkan dengan hampir rakus. Anda baru saja memulai jalan di suatu tempat dan mencoba untuk berjalan selama mungkin. Jika Anda mendeteksi sebuah lingkaran, Anda akan menghapus tepinya (tetapi catat bahwa lingkaran ini dibuat). Dengan ini, Anda menguraikan grafik dalam lingkaran, yang dapat dengan mudah digabungkan ke tur Euler. Intinya, tidak ada keputusan Anda "bagaimana berjalan melintasi grafik" yang sebenarnya bisa salah. Anda akan selalu berhasil dan tidak pernah macet.

Situasi dengan jalur Hamilton berbeda. Sekali lagi, Anda mungkin ingin membuat jalur dengan berjalan di sepanjang tepi grafik. Tetapi kali ini Anda benar-benar dapat membuat keputusan yang buruk . Ini berarti Anda tidak dapat melanjutkan jalan, tetapi tidak semua simpul telah dikunjungi. Apa yang dapat Anda lakukan adalah melacak kembali. Itu berarti Anda mengembalikan beberapa keputusan lama Anda dan melanjutkan di jalur yang berbeda. Pada dasarnya semua algoritma yang dikenal untuk masalah umum bergantung pada beberapa cara atau yang lain pada pelacakan-kembali, atau mencoba serangkaian solusi besar. Ini, bagaimanapun, adalah karakteristik untuk masalah NP-lengkap.

Jadi (disederhanakan) bottom-line: Jalur Euler tidak memerlukan pelacakan-kembali, tetapi jalur Hamilton tidak.

(Perhatikan bahwa mungkin P = NP dan dalam hal ini algoritma jalur Hamiltonian yang pintar akan ada.)

Detail lain yang dapat membantu intuisi Anda adalah bahwa siklus Euler ada jika dan hanya jika setiap titik memiliki derajat genap. Teorema serupa ada untuk jalur Euler. Ini mengikuti dari bukti yang cukup mudah - pada dasarnya, setiap kali Anda mengunjungi sebuah titik, Anda kemudian harus meninggalkannya, sehingga setiap "kunjungan" mengambil dua dari tingkat titik tersebut. Ini tidak menjelaskan mengapa jalur Hamiltonian sulit (yang, tentu saja, kita bahkan tidak benar-benar tahu), tetapi itu membantu menjelaskan mengapa menemukan jalur Euler mudah.

Victor Adamchik memberikan penjelasan yang baik tentang buktinya. Sebagian besar teori grafik / buku matematika diskrit kemungkinan akan memiliki bukti juga yang mungkin Anda temukan lebih mudah.

Jawaban lain memberikan intuisi yang bagus mengapa bukti sederhana seperti itu tampaknya tidak berhasil untuk siklus Hamilton.

"Apakah intuitif untuk melihat bahwa menemukan jalur Hamilton tidak dalam P sementara menemukan jalur Euler?"

Asumsi dalam pertanyaan Anda salah.

Perhatikan bahwa kita tidak tahu bahwa tidak ada di ! Seseorang suatu hari nanti mungkin menemukan karakterisasi yang sangat pintar dari (mirip dengan karakterisasi sebagai memiliki derajat genap) yang akan memasukkannya ke dalam .$\mathrm{HamPath}$$\mathsf{P}$$\mathrm{HamPath}$$\mathrm{EulerPath}$$\mathsf{P}$

Kebanyakan orang percaya bahwa itu tidak ada di tetapi tidak terbukti. Argumen (bukan bukti!) Mengapa tidak mungkin di sama dengan argumen untuk dan kebanyakan dari mereka tidak banyak bicara tentang sendiri selain dari fakta bahwa itu adalah .$\mathsf{P}$$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathrm{HamPath}$$\mathsf{NP\text{-}complete}$

Sekarang, Anda mungkin bertanya mengapa $\mathrm{HamPath}$ adalah $\mathsf{NP\text{-}complete}$ tapi kami tidak bisa menunjukkan itu $\mathsf{EulerPath}$ adalah $\mathsf{NP\text{-}complete}$? Karena seseorang telah menemukan karakterisasi yang ada di dalamnya$\mathsf{P}$ dan kemudian jawaban akan serupa dengan mengapa kita percaya itu $\mathsf{P} \neq \mathsf{NP}$ jadi tidak mungkin (tapi tidak terbukti!) itu $\mathsf{EulerPath}$ adalah $\mathsf{NP\text{-}complete}$.

Inilah satu cara cepat untuk melihatnya. Masalah HAM-PATH adalah$\mathsf{NP}$-lengkap, jadi saat ini kita tidak bisa jika bisa diselesaikan dalam waktu polinomial atau tidak. Setidaknya tidak ada yang datang dengan algoritma seperti itu. Masalah jalan Euler di sisi lain terbukti di$\mathsf{P}$karena kami memiliki algoritma waktu polinomial untuk itu. Sebuah$\mathsf{NP}$masalah-lengkap seperti HAM-PATH telah menolak serangan sejauh ini, jadi ini adalah salah satu cara langsung untuk melihat atau percaya itu lebih sulit daripada masalah di $\mathsf{P}$, katakanlah menemukan jalan Euler.