No exercício 7b podemos simplesmente usar o Teorema de Cook? Faço a pergunta porque se a resposta for sim a questão fica trivial e não é costumeiro encontrar questões triviais nessas listas.
A idéia é fazer a redução direto, sem usar o teorema de Cook.