7.22 and 7.24(b)

a. Show that SPATH e P. b. Show that LPATH is NP-complete. 722 Let DOUBLE-SAT ( ?) ? has at least two satisfying assignments). Show that DOUBLE-SAT is NP-complete. A723 Let HALF-CLIQUE = {(G) G is an undirected graph having a complete sub- aph with at least m/2 nodes, where m is the number of nodes in G). Show that HALF-CLIQUE is NP-complete. 724 1 et CNFk = t(o) o is a satisfiable cnf-formula where each variable appears in at most k places) a. Show that CNF2 P b. Show that CNFs is NP-complete. 7.25 Let CNFII {(o? ? s a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal). Show that CNFu E P 7.26 Let o be a 3enf-formula. An A-assignment to the variables of o is one whe