3-SAT の乱択アルゴリズム を使うことにより O(1.334V)O(1.334^V) 時間で解くことができます。