Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

SID: [No spaces and no dashes.]

Login ID : [e.g., cs170-xy]

1. Professor Ecru has come up with a new problem, FRIENDLIEST FOREST. She has proven that FRIENDLIEST FOREST is a search problem and that 3-COLORING can be reduced to FRIENDLIEST FOREST. Which of the following must necessarily be true, based on this information and what has been proven about P and NP? Which of the following cannot be true, based on this information and what has been proven about P and NP?

Does this result have any implications for the existence of polynomial-time for other problems you might be more familiar with or might have heard of? Why or why not?

4. How did you feel about the exam? Good/bad? Too easy/hard, short/long? Any concepts you expected less/more of?