Informacje o k-SAT (wprowadzenie, ograniczenia, metody itp.)

Chciałbym wiedzieć, gdzie mogę się zwrócić o dobre, delikatne wprowadzenie do k-SAT (może to być dla matematyków, którzy nie mają dobrego przygotowania informatycznego). Chciałbym również znać artykuły, które mogą przeglądać lub wyjaśniać obecne metody rozwiązywania k-SAT. Wreszcie interesują mnie najbardziej znane metody rozwiązywania k-SAT. Chciałbym dowiedzieć się, jaki jest najlepszy średni przypadek i najlepsze zachowanie w najgorszym przypadku.

Krótko mówiąc, szukam artykułów, które pomogą komuś z matematyki (nie informatyki) stać się znacznie bardziej ekspertem w dziedzinie k-SAT.

Z wątku referencyjnego Notatki z wykładu mamy ten dokument .

Ta książka ankietowa, Problem satysfakcji: Teoria i zastosowania , jest odpowiednia do wprowadzenia matematyki do K-SAT. Nie jest to najnowszy, ale wciąż bardzo cenny zasób.