Информация о k-SAT (введение, границы, методы и т. Д.)

9

Я хотел бы знать, куда я могу обратиться за хорошим, мягким введением в k-SAT (это может быть для математиков, которые могут не иметь хорошего компьютерного фона). Я также хотел бы знать статьи, которые, возможно, опрашивают или объясняют текущие методы, используемые для решения k-SAT. Наконец, меня интересуют самые известные методы решения k-SAT. Я хотел бы получить представление о лучшем среднем и худшем поведении.

Короче говоря, я ищу документы, которые помогут кому-то в математике (не информатике) стать большим экспертом в k-SAT.

Мэтт Грофф
источник
1
На сайте есть несколько хороших ответов о k-SAT: примечания к лекциям , верхние и нижние границы, со многими ссылками внутри. Попробуйте поискать по тегу сат тоже.
Сянь-Чи Чанг 之 之

Ответы: