Consider a set $A=a_l,$dots,$a_n$ and a collection $B_1,B_2,$dots,$B_m$ of subsets of

A $($i$.$e$.,B_i$subeA for each $i).$ We say that a set HsubA is a hitting set for the collection

$B_1,B_2,$dots,$B_m$

if $H$ contains at least one element from each $B_i,$ that is$,$ if $H{B}_i\frac{O}{?}$ for each $i($so $H$ "hits" all

the sets $B_i).$ We now define the Hitting Set Problem as follows. We are given a set $A=a_l,$dots,$a_n,$

a collection $B_1,B_2,$dots,$B_m$ of subsets of $A,$ and a number $k.$ We are asked: Is there a hitting set

HsubA for $B_1,B_2,$dots,$B_m$ such that the size of $H$ is at most $k?$

Show that $3-$SAT${?}_p$ Hitting Set'.

Hint: Design an algorithm so that it converts a $3-$CNF$-$formula $$ with $m$ clauses over $n$

variables into an instance of Hitting Set with

The universe that has $2n$ elements $($one for each literal in $),$

The collection that contains exactly $m+n$ sets. Moreover $n$ sets in the

collection contain exactly $2$ elements.

The requested size of the actual hitting set in this instance is $n.$