Problem $8.$ A $k-$CNF formula is a conjunction $($AND$)$ of a set of clauses, where each

clause is a disjunction $($OR$)$ of a set of exactly $k$ literals. For example,

$(avvbvvcvvnotdvvnote{)}^{{?}^{?}}(notavvbvvcvvnotxvvnoty{)}^{{?}^{?}}(notxvvyvvcvvdvva)$

is a $5-$CNF$.$ The $k-$SAT problem asks if a $k-$CNF formula is satisfiable. In class we saw that $3-$SAT

is NP$-$hard. In contrast, $2-$SAT is polynomially solvable, as it is mentioned in GA$4.$

$($a$)$ Show that $4-$SAT is NP$-$Complete $($For partial credit, specify all the statements you need to

conclude that $4-$SAT is NP$-$complete even if you cannot prove them$).$

$($b$)$ Describe a polynomial time algorithm to solve $1-$SAT.