Reputation: 11
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?
Upvotes: 0
Views: 148
Reputation: 445
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.
Upvotes: 1