4 ms·
2SAT is boring because given a clause with one unfulfilled literal, you know the other literal must be satisfied. There's no choice to be made. This limits back
by lorenzhs 9y ago
2SAT is boring because given a clause with one unfulfilled literal, you know the other literal must be satisfied. There's no choice to be made. This limits backtracking enormously. It can even be solved in linear time (although that's nontrivial)