Answer Happy

b An instance of the problem AlmostSAT is
a CNF Boolean formula containing at least 2 clauses, plus the
index number of a clause in that formula. For example an
instance of AlmostSAT could be represented as:
'(X2 OR X3) AND (NOT X3) AND (NOT X2);1'
A positive instance is one in which there is a variable
assignment that satisfies all the clauses, except
possibly the one specified by the index number. The
example above is a positive instance of AlmostSAT because '(X2 OR
X3) AND (NOT X2)' can be satisfied by setting X2 to False
and X3 to True.
Like SAT, a positive instance
of SAT¬ℇ is a satisfiable CNF
Boolean formula. The only difference is thatan instance of
SAT¬ℇ must contain at least one clause.
Prove that AlmostSAT and
SAT¬ℇ are
polyequivalent. That is, prove that AlmostSAT ≤p
SAT¬ℇ, and that
SAT¬ℇ ≤
AlmostSAT. (Show that positive instances can be
mapped to positive instances, negative to negative.)