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.
[No spaces and no dashes.]
Login ID :
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?