2 ms·
The conversion to DNF is fine. The original clauses map directly to pairs of new clauses, so fixing an assignment to the original variables V you can always sat
by pfedak 3y ago
The conversion to DNF is fine. The original clauses map directly to pairs of new clauses, so fixing an assignment to the original variables V you can always satisfy the same number of the DNF clauses. You can do worse by choosing the wrong values for X, sure, but there's always a straightforward correspondence.