CS 170 Reading Quiz -- Week 13, Monday

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.

Name:

SID: [No spaces and no dashes.]

Login ID :

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

  1. FRIENDLIEST FOREST is in P.
  2. FRIENDLIEST FOREST is in NP.
  3. If it is possible to solve FRIENDLIEST FOREST in polynomial time, it is possible to solve 3-COLORING in polynomial time.
  4. It is possible to solve FRIENDLIEST FOREST in polynomial time.
  5. It is impossible to solve FRIENDLIEST FOREST in polynomial time.
  6. It is possible to solve FRIENDLIEST FOREST in exponential time.
You can just provide a list of the numbers of the ones that must be true, without explanation or justification.

2. Now answer the same question, but this time list which ones could be true, based on the information provided and what has been proven about P and NP. You do not need to justify or explain your answer.

(For instance, it could be true that P=NP, because no one has proven the contrary; but it couldn't be true that 1+1=3, because this is provably false.)

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page