$3.$ The hitting set problem takes in a set $\backslash ($ X $\backslash ),$ a family $\backslash ($ F $\backslash )$ of subsets of $\backslash ($ X $\backslash ),$ and an integer $\backslash ($ k $\backslash ),$ and returns whether there is some subset of $\backslash ($ X $\backslash )$ of size $\backslash ($ k $\backslash )$ that overlaps every element of $\backslash ($ F $\backslash ).$ For example, if $\backslash ($ X$=\backslash \{1,2,3,4\backslash \},$ F$=\backslash \{[1,2],[2,3],[3,4],[4,1]\backslash \}\backslash ),$ and $\backslash ($ k$=2\backslash ),$ the set $\backslash (\backslash \{2,4\backslash \}\backslash )$ is a solution, since $2$ overlaps the first two sets in F $("$hits$"$ them$)$ and $4$ overlaps the other two.

The $3-$CNF Satisfiability problem $(3$SAT$)$ takes in a Boolean expression in $3-$CNF and returns whether that expression is satisfiable. A Boolean expression in $3-$CNF has a set of clauses joined by "ands," where each clause is $3$ literals joined by "ors."

Answer the following questions about the reduction algorithm below.

$```$

Input: C: set of clauses in $3-$CNF form $(3$ literals per clause$)$

Input: n: number of variables in the clauses

Input: m: number of clauses

Output: whether there is some assignment of variables $\}\backslash$mp@subsup$\{$v$\}\{1\}\{\},\backslash$mp@subsup$\{$v$\}\{2\}\{\},\backslash$ldots$,\backslash$mp@subsup$\{$v$\}\{$n$\}\{\}\backslash$mathrm$\{$ such

that every clause in C is satisfied by at least one of its three literals

Algorithm: HittingSetReduction

X $=\{\}$;

F $=\{\}$;

k$=$n;

for i$=1$ to n do

Add vi and $\backslash$

Add $\{\backslash$mp@subsup$\{$v$\}\{$i$\}\{\},\backslash$overline$\{$v$\}$

end

for i$=1$ to m do

Let c be the $3$ literals in C$[$i$]$;

Add c to F;

end

return HittingSet$($X$,$F$,$k$)$;

$```$

$($a$)[10$ points$]$ What is the worst$-$case time complexity for HittingSetReduction? Justify your answer.

$($b$)[10$ points$]$ Does HittingSetReduction prove that Hitting Set is NP$-$Hard if $3-$SAT is NPHard, or does it prove that $3-$SAT is NP$-$Hard if Hitting Set is NP$-$Hard? Justify your answer.