Suppose M’ is a TM that semidecides a language L

Description

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 x^cj 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 )

2. Show that 2SAT Î P

5 – Given an EC problem with U = { u0, u1 , u2 , u3 , u4 } ;

6. = { {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.