2-SAT and Max 2-SAT
Kent Quanrud · 78:58
2SAT is solvable in linear time via an implication graph and strongly connected components, but Max-2SAT is as hard as 3SAT/Boolean SAT. The lecture’s point is that two nearly identical problems—decide whether every 2...