Apakah grafik masalah decidable terbatas ini? Faktor-faktor apa membuat masalah decidable?

Aku ingin tahu apakah masalah berikut adalah decidable dan bagaimana untuk mencari tahu. Setiap masalah yang saya lihat saya dapat mengatakan "ya" atau "tidak" untuk itu, jadi apakah sebagian besar masalah dan algoritma dapat dipilih kecuali beberapa (yang disediakan di sini )?

Input: Grafik berarah dan berhingga , dengan dan sebagai simpul. Pertanyaan: Apakah jalur dalam dengan sebagai simpul awal dan sebagai simpul akhir ada?v u G u $G$$v$$u$
$G$$u$$v$

Setiap masalah yang membutuhkan hanya memeriksa jumlah terbatas data decidable, karena ada suatu algoritma yang terdiri dari enumerasi semua solusi potensial. Mungkin ridiculously lambat, tapi itu tidak relevan: jika ada sebuah algoritma, itu decidable.

Masalah yang Anda nyatakan mengasumsikan grafik terbatas, yang sangat mengisyaratkan bahwa grafik tersebut dapat ditentukan. Sebenarnya, Anda perlu melihat sedikit lebih jauh. Masalahnya adalah properti di jalur di grafik, dan kadang-kadang ada jumlah jalur yang tak terbatas, ketika grafik berisi siklus (Anda dapat mengulangi siklus ini sebanyak yang diinginkan). Namun, mudah untuk mengubah masalah menjadi masalah yang terbatas: jika ada jalur yang dimulai dengan dan berakhir dengan v yang mencakup siklus, maka Anda dapat memotong semua siklus di jalur itu, dan Anda memiliki solusi baru yang tidak tidak termasuk siklus. Karena ada sejumlah terbatas jalur yang tidak melibatkan siklus (jika grafik memiliki tepi k , maka paling banyak k $u$$v$$k$$k!$jalur yang tidak menggunakan tepi yang sama lebih dari sekali), masalah menemukan jalur dari ke v adalah terbatas, karenanya dapat diputuskan.$u$$v$

Kebetulan, properti ini disebut konektivitas .

Pendekatan ini adalah yang umum, yang disebut reduksi . Mengingat masalah yang tidak langsung, kami menguranginya menjadi masalah yang kami tahu bagaimana menyelesaikannya.

Seringkali sulit untuk membuktikan bahwa suatu masalah tidak dapat diputuskan. Untuk membuktikan bahwa masalah dapat diputuskan, yang perlu kita lakukan adalah menunjukkan algoritma yang memutuskannya. Untuk membuktikan bahwa masalah tidak dapat diputuskan, kita perlu membuktikan bahwa tidak ada algoritma yang bisa ada. Ada beberapa masalah yang tidak dapat dipastikan yang diketahui. Dalam praktiknya, sebagian besar waktu, ketika kami membuktikan bahwa suatu masalah tidak dapat diputuskan, kami menunjukkan bahwa ada masalah yang tidak dapat dipastikan yang terkenal yang mengurangi masalah kami. Karena algoritme untuk masalah kita akan menyelesaikan masalah yang tidak dapat ditentukan yang diketahui, masalah kita juga harus tidak dapat diputuskan.

Anda tidak dapat mengatakan bahwa “sebagian besar” masalah dapat diputuskan atau “sebagian besar” masalah tidak dapat diputuskan. Dalam beberapa pengertian teoretis, hampir semua masalah tidak dapat diputuskan, tetapi kami memiliki kecenderungan yang kuat untuk mengatasi masalah "menarik", dan mereka lebih cenderung memiliki solusi.

Masalahnya sepele diputuskan, seperti yang ditunjukkan oleh Gilles dalam komentar. Adapun pertanyaan Anda yang lain ...

sebagian besar masalah dan algoritma dapat dipilih kecuali beberapa (yang disediakan di sini )?

Nggak. Sebenarnya, sebagian besar masalah tidak dapat diputuskan. Sebenarnya, ada banyak masalah (bahasa) yang tak terhitung jumlahnya, tetapi hanya ada banyak Mesin Turing yang dapat dihitung, yang berarti ada paling banyak masalah yang dapat diperhitungkan.

Ya, ini dapat dipilih, karena Anda dapat melakukan pencarian lengkap dari semua jalur yang mungkin. Tidak perlu melihat jalur yang mengulangi titik, karena "jalan memutar" dapat dilewati. Tetapi panjang dari setiap jalur non-berulang dibatasi oleh ukuran grafik, yang terbatas, sehingga hanya ada banyak jalur seperti itu, yang dapat diperiksa satu per satu.

$G$$a$$b$$a$$b$

Tidak ada metode yang memberi tahu Anda apakah masalah tertentu dapat ditentukan atau tidak. Dengan berjalannya waktu, Anda mungkin mendapatkan "firasat" baik apakah masalah tertentu dapat ditentukan atau tidak.

Apa yang biasanya saya lakukan adalah sebagai berikut:

1. coba selesaikan masalahnya. Artinya, coba pikirkan program komputer yang memecahkan masalah yang diberikan. Untuk masalah Anda disarankan - program yang sangat sederhana hanya akan memeriksa jalan apapun mungkin dan dengan demikian akan selalu berhasil menemukannya (jika ada), atau memberitahu Anda tidak ada jalan ada sebaliknya.
2. merumuskan masalah dengan jelas. Banyak masalah yang terlalu samar-samar, tapi ketika ditulis jelas sangat mudah untuk melihat apakah decidable atau tidak (dengan membandingkan masalah lain, dikenal un / decidable, atau dengan menggunakan metode terkenal seperti teorema Rice )
3. Jika (2) tidak bekerja tetapi Anda masih percaya masalahnya adalah diputuskan, mencoba untuk membuktikannya dengan pengurangan dari masalah diputuskan (masalah yang terputus-putus (atau pelengkap) bekerja untuk banyak kasus).

Hampir selalu, ketika mencoba untuk melakukan langkah (1) untuk masalah diputuskan, Anda akan membutuhkan program Anda untuk memeriksa terbatas jumlah hal. Ini biasanya merupakan pertanda bahwa masalahnya tidak dapat diputuskan.