HW6
0- Suppose M’ is a TM that semidecides a language L . Construct a TM M making use
of M’ that semidecides the language L*.
1- Prove the transitivity of the polynomial reduction operator a :
i.e. , L1 a L2 and L2 a L3 implies that L1 a L3
2 - Given a SAT problem define a set of literals in SAT a consistent set if a literal xj
and its complement literal xc
j are NOT both members of this set.
Prove that SAT has a solution if and only if there exists a consistent set of literals,
whose members are selected, one from each clause Cj .
3 - Prove the following : IS a CLIQUE , IS a NC, SAT a MAXSAT, HC a UHC
where IS= Independent Set , NC = Node Cover and UHC = HC for undirected
graphs.
4- (a) Formulate the 2SAT problem where each vertex corresponds to a Boolean
literal and there is a directed edge from vertex x to vertex y corresponding to x
implies y (x Þ y or ¬x Ú y or (¬x, y) is a clause )
(b) Show that 2SAT Î P
5 - Given an EC problem with U = { u0, u1 , u2 , u3 , u4 } ;
F = { {u0 , u3, u4},{u2 ,u4},{u0, u1,u2}, {u0, u2, u4},{u1, u2} }
State the KS and the HC problems obtained from the above EC problem by the
polynomial reduction methods discussed in class. State solution(s) of the three
problems EC , KS and HC if one exists for each case.
