Understanding P$,$ NP$,$ and poly$-$time mapping reductions.

$(5$ pts$)$ We claim that $($a$)$ P $$ NP$,$ i$.$e$.,$ for any language L in P$,$ we have that L in NP as well. Here

is an incomplete proof of this fact, which you will complete.

By the hypothesis that L in P$,$ there is an efficient Turing machine M that decides L$.$ We

define the following efficient verifier V for L$.$

$1$: function V $($x$,$ c$)$

$2$: $[$MISSING PSEUDOCODE$]$

State what the missing pseudocode should be$,$ and prove that V is indeed an efficient

verifier for L$.$

Solution:

$(8$ pts$)$ Show that poly$-$time mapping reductions are transitive. That is$,$ if $($b$)$ A $<=$p B and B $<=$p C$,$

then A $<=$p C$.$

Solution:

$(8$ pts$)$ Let $($c$)$ C $=$ A $\backslash$cup B where both A$,$ B are languages in NP$.$ State, with proof, whether C is in

NP for all, some $($but not all$),$ or no such A$,$ B$.$