$2.$ A clause $($i$.$e$.$ a disjunction of literals$)$ is called a Horn clause, if it contains at most one positive literal. Such a clause can be written as an implication; e$.$g$.(\backslash ($

eg x $\backslash$vee y $\backslash$vee

eg z $\backslash$vee

eg u $\backslash ))$ is equivalent to

$\backslash [$

$($x $\backslash$wedge z $\backslash$wedge u$)\backslash$rightarrow y

$\backslash ]$

HORNSAT is the problem of deciding whether a given Boolean formula, which is a conjunction of Horn clauses, is satisfiable.

$($a$)$ Show that there is a polynomial algorithm for solving HORNSAT. $($Hint: if a variable is the only literal in the clause, it must be set to T ; if all the negative variables in the clause have been set to T $,$ then the positive one must also be

set to T$.$ Continue this procedure until a contradiction is reached or a satisfying assignment is found.$)$

$($b$)$ In the proof of the NP$-$completeness for SAT, it was shown how to construct, for every nondeterministic Turing machine $\backslash ($ M $\backslash ),$ integer $\backslash ($ k $\backslash ),$ and a string $\backslash ($ x $\backslash ),$ a Boolean expression $\backslash (\backslash$phi$=$f$($x$)\backslash ),$ which is satisfiable if$,$ and only if$,\backslash ($ M $\backslash )$ accepts $\backslash ($ x $\backslash )$ in at most $\backslash ($ n$^\{$k$\}\backslash )$ steps. Show that, if $\backslash ($ M $\backslash )$ is deterministic, then $\backslash (\backslash$phi $\backslash )$ can be chosen to be a conjunction of Horn clauses.

$($c$)$ Conclude from $($b$)$ that the problem HORNSAT is P complete.