Problem
1. Show that a problem is NP-easy if and only if it reduces to an NP-complete problem.
2. Suppose that problem A and problem B are two different decision problems. Furthermore, assume that problem A is polynomial-time many-one reducible to problem B. If problem A is NP-complete, is problem B NP-complete? Justify your answer.
3. When all instances of the CNF-Satisfiability problem have exactly three literals per clause, it is called the 3-Satisfiability problem. Knowing that the 3-Satisfiability problem is NP-complete, show that the Graph 3-Coloring problem is also Complete.