SAT and 3SAT

preview_player
Показать описание
Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.

Lecture slides by K. Wayne accompanying the latter textbook:
Рекомендации по теме
Комментарии
Автор

Since the literals in a given clause are connected in the triangle, it is obvious that you cannot construct an independent set by picking two vertices from one triangle. But what would it mean in terms of the 3SAT problem if you did? For example if you picked x2 and x3 in the first triangle, then does this mean that x2 and x3 cannot both be true as this would not lead to a satisfying assignment?

confluenceking