Informasi tentang k-SAT (Pendahuluan, Batas, Metode, dll.)

Saya ingin tahu di mana saya bisa berpaling untuk pengantar k-SAT yang bagus dan lembut (ini mungkin untuk ahli matematika yang mungkin tidak memiliki latar belakang ilmu komputer yang baik). Saya juga ingin tahu makalah yang mungkin mensurvei atau menjelaskan metode saat ini yang digunakan untuk menyelesaikan k-SAT. Akhirnya, saya tertarik pada metode yang paling dikenal untuk memecahkan k-SAT. Saya ingin mendapat gambaran tentang kasus rata-rata terbaik dan perilaku kasus terburuk terbaik.

Singkatnya, saya mencari makalah yang akan membantu seseorang dalam matematika (bukan ilmu komputer) menjadi jauh lebih ahli dalam k-SAT.

Dari utas referensi Catatan Kuliah, kami memiliki dokumen ini .

Buku survei ini, Masalah Kepuasan: Teori dan Aplikasi , sesuai untuk memperkenalkan k-SAT kepada ahli matematika. Ini bukan sangat baru tetapi masih sumber daya yang sangat berharga.