Maria S.
Maria S.

Reputation: 11

Flip/change satisfiability of SAT problem

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

Answers (1)

Gregory Morse
Gregory Morse

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

Related Questions