2-SAT and max 2-SAT (Fundamental algorithms, Spring 2023, Lecture 10)
Kent Quanrud · 73:34
Two-SAT is solvable in linear time by building an implication graph and checking that no variable and its negation share a strongly connected component; Max-2-SAT looks similar but is NP-hard, shown by reducing 3-SAT...