Mengapa tidak ada algoritma perkiraan untuk SAT dan masalah keputusan lainnya?

Saya memiliki masalah keputusan NP-lengkap. Diberikan contoh masalah, saya ingin merancang algoritma yang menampilkan YA, jika masalahnya layak, dan, TIDAK, jika tidak. (Tentu saja, jika algoritme tidak optimal, itu akan membuat kesalahan.)

Saya tidak dapat menemukan algoritma perkiraan untuk masalah seperti itu. Saya sedang mencari secara khusus untuk SAT dan saya menemukan di halaman Wikipedia tentang Algoritma Aproksimasi sebagai berikut: Keterbatasan lain dari pendekatan ini adalah bahwa itu hanya berlaku untuk masalah optimasi dan bukan untuk masalah keputusan "murni" seperti kepuasan, meskipun seringkali mungkin untuk .. .

Mengapa kita tidak, misalnya, mendefinisikan rasio perkiraan menjadi sesuatu yang proporsional dengan jumlah kesalahan yang dibuat oleh algoritma? Bagaimana kita benar-benar menyelesaikan masalah keputusan secara serakah dan tidak optimal?

Algoritma pendekatan hanya untuk masalah optimasi, bukan untuk masalah keputusan.

Mengapa kita tidak mendefinisikan rasio aproksimasi sebagai pecahan dari kesalahan yang dilakukan algoritma, ketika mencoba menyelesaikan beberapa masalah keputusan? Karena "rasio aproksimasi" adalah istilah dengan makna standar yang didefinisikan dengan baik, yang berarti sesuatu yang lain, dan itu akan membingungkan untuk menggunakan istilah yang sama untuk dua hal yang berbeda.

OK, bisakah kita mendefinisikan beberapa rasio lain (sebut saja itu sesuatu yang lain - misalnya, "rasio-det") yang menghitung jumlah kesalahan yang dibuat algoritma, untuk beberapa masalah keputusan? Tidak jelas bagaimana cara melakukannya. Apa yang akan menjadi penyebut untuk fraksi itu? Atau, dengan kata lain: akan ada jumlah contoh masalah yang tak terbatas, dan bagi sebagian dari mereka algoritma akan memberikan jawaban yang benar dan yang lain akan memberikan jawaban yang salah, sehingga Anda berakhir dengan rasio yang "Sesuatu dibagi dengan tak terbatas", dan yang akhirnya menjadi tidak berarti atau tidak didefinisikan.

Sebagai alternatif, kita dapat mendefinisikan sebagai fraksi kesalahan kesalahan algoritma, pada contoh masalah ukuran n . Kemudian, kita dapat menghitung batas r n sebagai n → ∞ , jika ada batas seperti itu. Ini akan$r_n$$n$$r_n$$n \to \infty$harus didefinisikan dengan baik (jika ada batasnya). Namun, dalam kebanyakan kasus, ini mungkin tidak terlalu berguna. Secara khusus, secara implisit mengasumsikan distribusi yang seragam pada contoh masalah. Namun, di dunia nyata, distribusi aktual pada contoh masalah mungkin tidak seragam - seringkali sangat jauh dari seragam. Akibatnya, jumlah yang Anda dapatkan dengan cara ini sering kali tidak berguna seperti yang Anda harapkan: sering memberi kesan menyesatkan tentang seberapa baik algoritma tersebut.

Untuk mempelajari lebih lanjut tentang bagaimana orang-orang berurusan dengan kepraktisan (NP-hardness), lihat Menangani masalah kepraktisan: masalah lengkap NP .

Alasan Anda tidak melihat hal-hal seperti rasio perkiraan dalam masalah pengambilan keputusan adalah bahwa mereka umumnya tidak masuk akal dalam konteks pertanyaan yang biasanya ditanyakan tentang masalah pengambilan keputusan. Dalam pengaturan optimasi, masuk akal karena berguna untuk menjadi "dekat." Di banyak lingkungan, itu tidak masuk akal. Tidak masuk akal untuk melihat seberapa sering Anda "dekat" dalam masalah logaritma diskrit. Tidak masuk akal untuk melihat seberapa sering Anda "dekat" untuk menemukan grafik isomer. Dan juga, dalam kebanyakan masalah pengambilan keputusan, tidak masuk akal untuk "dekat" dengan keputusan yang tepat.

Sekarang, dalam implementasi praktis, ada banyak kasus di mana membantu mengetahui bagian mana dari masalah yang dapat diputuskan "dengan cepat" dan bagian mana yang tidak bisa. Namun, tidak seperti optimisasi, tidak ada cara satu ukuran yang cocok untuk mengukur ini. Anda dapat melakukannya secara statistik, seperti yang Anda sarankan, tetapi hanya jika Anda mengetahui distribusi statistik dari input Anda. Sebagian besar waktu, orang-orang yang tertarik dengan masalah keputusan tidak begitu beruntung memiliki distribusi seperti itu.

Sebagai studi kasus, pertimbangkan masalah penghentian. Masalah penghentian diketahui tidak dapat diputuskan. Ini memalukan, karena ini adalah masalah yang sangat berguna untuk dapat diselesaikan jika Anda membuat kompiler. Namun dalam praktiknya, kami menemukan bahwa sebagian besar program sebenarnya sangat mudah dianalisis dari perspektif masalah yang terhenti. Compiler memanfaatkan ini untuk menghasilkan kode optimal dalam keadaan ini. Namun, kompilator harus menyadari bahwa ada kemungkinan kode tertentu tidak dapat ditentukan. Program apa pun yang bergantung pada kode yang "mungkin dapat dipilih" bisa mendapat masalah.

Namun, metrik yang digunakan oleh kompiler untuk menentukan seberapa baik yang mereka lakukan dalam menyelesaikan kasus-kasus khusus dari masalah penghentian ini sangat berbeda dari metrik yang digunakan oleh program kriptografi untuk menguji apakah pasangan bilangan prima tertentu dapat dikeraskan dengan kuat terhadap serangan. Tidak ada satu ukuran cocok untuk semua solusi. Jika Anda menginginkan metrik seperti itu, Anda ingin menyesuaikannya agar sesuai dengan ruang masalah dan logika bisnis Anda.

Selain jawaban yang ada, izinkan saya menunjukkan bahwa ada situasi di mana masuk akal untuk memiliki solusi perkiraan untuk masalah keputusan, tetapi berfungsi berbeda dari yang Anda kira.

Dengan algoritma ini, hanya satu dari dua hasil yang ditentukan dengan pasti, sedangkan yang lainnya mungkin salah. Ambil tes Miller-Rabin untuk bilangan prima , misalnya: Jika tes menentukan bahwa bilangan tidak prima, hasilnya pasti. Tetapi dalam kasus lain itu hanya berarti bahwa jumlahnya mungkin prima. Bergantung pada berapa banyak waktu komputasi yang ingin Anda investasikan, Anda dapat meningkatkan kepercayaan diri Anda pada hasilnya, tetapi itu tidak akan 100% karena untuk kasus yang tidak utama.

Ini sangat kuat ketika menangani masalah yang tidak dapat diputuskan: Anda bisa menulis alat yang mencoba memecahkan masalah penghentian untuk bagian kode tertentu. Jika dapat menemukan bukti bahwa program tidak akan berulang tanpa henti, Anda dapat mengklaimnya dengan kepastian 100%. Jika Anda tidak dapat menemukan bukti seperti itu, mungkin saja alur kontrol program terlalu berbelit-belit untuk dianalisis alat Anda, tetapi itu bukan bukti bahwa itu akan berulang selamanya. Dengan menyederhanakan struktur kontrol, Anda mungkin dapat membuat program yang setara yang cukup sederhana untuk alat untuk membuktikan bahwa itu akan berhenti secara pasti.