Show that the polynomial-time mapping reducibility ?pm is a transitive relation; that is, for all languages A, B, and C, A ?pm B and B ?pm C implies A ?pm C.

(50 points) Define H-[(M,k) | M is an NFA, k is an integer, and there is no NFA with at most k states that accepts the same language as H}. Show that SAT is mapping-reducible to H in the following manner: (a) (40 points) Let ?-C1 ? ? Cm be a 3CNF formula with some n variables and some m clauses. We can view each 0/1-sequence having length n as a truth- assignment to the variables of ?, where for each i, 1-2-n, the i-th bit of the sequence represents the value given to the i-th variable of ?. i. (10 points) For each i, 1 i ? m, let Li = {x | x is a 0/1 sequence having length n that represents a truth-assignment that fails to satisfy Ci}. Show that for each i, i-i-m, there exists an NFA with n+ 1 states for Li ii. (10 points) Show that there is a DFA with n + 2 states for Lo -Ix r is a 0/1 sequence whose length is not equal to n iii. (5 points) Define L to be the union of Lo, L?,-.. , Lm. Using the above two results, show that there is an NFA with at most (m+1)(n+1) +1 states for iv. (10 points) Show that ? is not satisfiable if and only if L-10, 1 v. (5 points) Show that there is a one-state NFA (actually DFA) for [0,1)* (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H. (50 points) Define H-[(M,k) | M is an NFA, k is an integer, and there is no NFA with at most k states that accepts the same language as H}. Show that SAT is mapping-reducible to H in the following manner: (a) (40 points) Let ?-C1 ? ? Cm be a 3CNF formula with some n variables and some m clauses. We can view each 0/1-sequence having length n as a truth- assignment to the variables of ?, where for each i, 1-2-n, the i-th bit of the sequence represents the value given to the i-th variable of ?. i. (10 points) For each i, 1 i ? m, let Li = {x | x is a 0/1 sequence having length n that represents a truth-assignment that fails to satisfy Ci}. Show that for each i, i-i-m, there exists an NFA with n+ 1 states for Li ii. (10 points) Show that there is a DFA with n + 2 states for Lo -Ix r is a 0/1 sequence whose length is not equal to n iii. (5 points) Define L to be the union of Lo, L?,-.. , Lm. Using the above two results, show that there is an NFA with at most (m+1)(n+1) +1 states for iv. (10 points) Show that ? is not satisfiable if and only if L-10, 1 v. (5 points) Show that there is a one-state NFA (actually DFA) for [0,1)* (b) (10 points) Using the above observations, show that SAT is polynomial-time map- ping reducible to H