Bagaimana membuktikan bahwa 3-pewarnaan dapat dipilih?

9

Untuk membuktikan bahwa 3-pewarnaan dapat dipilih, apakah cukup untuk mengatakan:

  • Setiap node dalam grafik memiliki 3 warna yang memungkinkan
  • Karena itu kita dapat menghitung semua kemungkinan dan kemudian memeriksa bahwa tidak ada dua sisi yang menghubungkan node dengan warna yang sama3n

Apakah itu membuktikan bahwa 3-pewarnaan dapat dipilih? Atau apakah saya perlu membuat mesin Turing untuk bukti yang benar?

Dengan 3-pewarnaan saya berbicara tentang masalah pewarnaan grafik; yaitu menetapkan satu dari 3 warna untuk setiap node dalam grafik yang tidak diarahkan sedemikian rupa sehingga tidak ada dua node yang berdekatan memiliki warna yang sama.

computability turing-machines colorings Jenny
sumber
5
Ini cukup baik untukku. Omong-omong, bahkan jika Anda ingin menjadi sangat formal, Anda tidak harus menyediakan mesin Turing; sebuah program dalam bahasa lengkap Turing akan cukup. (Memang, bahasanya tidak perlu Turing-complete, kita hanya perlu mendefinisikan fungsi yang dapat dihitung.)
Yuval Filmus
Bagi kebanyakan orang, hal itu memang benar. Dalam kursus pengantar mungkin tidak. Juga, bagi sebagian orang "bukti formal" berarti sesuatu yang berbeda, yang mungkin Anda lihat jika Anda mengambil kursus tentang logika.
Yuval Filmus
@YuvalFilmus Terima kasih. Seperti apa "bukti formal" dalam konteks mata kuliah logika, dapatkah Anda menunjukkan saya pada contoh?
Jenny
@ Jenny Jika Anda tertarik, ikuti kursus logika.
Yuval Filmus
@YuvalFilmus Saya tidak memiliki akses ke kursus logika, apakah ada buku atau sumber daring yang dapat Anda rekomendasikan?
Jenny

Jawaban:

10

Itu sepenuhnya tergantung pada tingkat formalitas yang Anda tuju. Deskripsi informal suatu algoritma dalam pertanyaan Anda cukup untuk meyakinkan saya bahwa 3-colourability dapat dipilih. Jika Anda ingin menjadi lebih formal, Anda bisa memberikan kodesemu. Jika Anda ingin lebih formal, Anda bisa menggambarkan mesin Turing dalam bahasa Inggris. Jika Anda ingin menjadi lebih formal, Anda bisa menuliskan deskripsi lengkap dari mesin Turing dan membuktikan bahwa itu benar-benar menentukan 3-colourability.

Karena itu, dari opsi yang saya daftarkan, kemungkinan besar akan ada kesalahan dalam deskripsi mesin Turing atau dalam bukti kebenarannya! Jadi tidak jelas bukti mana yang paling bisa dipercaya.

David Richerby
sumber
-5

Semua masalah non deterministik untuk TM dapat diputuskan, jadi dari uraian Anda, Anda menunjukkan bahwa Anda memerlukan mesin untuk memvalidasi suatu solusi. Jadi penjelasan Anda sudah cukup.3n

Juan Manuel Dato Ruiz
sumber
2
Hai, selamat datang di CS. Sayangnya, kiriman Anda sepertinya tidak menjawab pertanyaan dengan penuh arti.
vonbrand