# CS 170 Reading Quiz -- Week 11, Tuesday

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

Name:

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?

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

2. Suppose that tomorrow a group of researchers announce a mathematical proof that there is no polynomial-time algorithm for ROUNDEST INVERTIBLE LATIN SQUARE. You've never heard of ROUNDEST INVERTIBLE LATIN SQUARE before, and it sounds like pretty esoteric stuff, but you know that it is a search problem (i.e. the ROUNDEST INVERTIBLE LATIN SQUARE problem is in NP). This is hailed as a huge breakthrough in CS theory, but you can't help wondering whether you should care.

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?

3. What did you find difficult or confusing about the reading for the upcoming lecture, 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.

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