1. 2,3,6. Explanations (which you didn't need to provide): 1: Not necessarily. 2: Must be true. NP is defined to be the set of all search problems, and the problem statement said that FRIENDLIEST FOREST is a search problem. 3: Definitely true. The reduction gives us an algorithm for solving 3-COLORING, using a subroutine that solves FRIENDLIEST FOREST; and the total running time is at most the time the subroutine takes, plus polynomial time. So if the subroutine only needs polynomial time, the algorithm for 3-COLORING will run in polynomial time as well. 4: Not necessarily. 5: Not necessarily. It might be possible to solve FRIENDLIEST FOREST in polynomial time: this would happen, for instance, if P = NP, which we can't rule out. 6: Definitely true. Every search problem can be solved in exponential time: since you have a way to recognize the correct answer in polynomial time, just try all possibilities and you'll find the correct answer after trying at most exponentially many possibilities. 2. 1,2,3,4,5,6 -- all of them. Explanations (which you didn't need to provide): 1: Yeah, there might be some polynomial time algorithm for FRIENDLIEST FOREST, for all we know. 2: See above; it must be true. 3: See above; it must be true. 4: Certainly possible. This is equivalent to item 1. 5: Certainly possible. Maybe P != NP and FRIENDLIEST FOREST is one of the search problems that cannot be solved in polynomial time. 6: See above; it must be true. I'd also accept 1,4,5 as correct (if you thought that "could be true" excludes everything that "must be true").