Flip/change satisfiability of SAT problem

82 Views Asked by At

Is there a way to change the satisfiability of a SAT problem without knowing whether the original problem is satisfiable or not beforehand?

There are satisfiability-preserving operations like removing supersets or resolution that maintain the satisfiability status of a problem independent of its label. Is there a way to do the opposite?

1

There are 1 best solutions below

0
Gregory Morse On

Yes, you can delete all of the clauses except for one, and then as long as this is not a falsity clause, it is guaranteed to be satisfiable as the base case of unsatisfiability is False and then A&~A.