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?