CS 170 Reading Quiz -- Week 14, Tuesday

WARNING: There seem to be some problems in quiz submission. I am looking into it. I will issue an extension until Tuesday morning, 10am. In the meantime, please check carefully the response message to see whether your quiz submission was accepted or not. If you receive an error message, you will need to re-submit. -- David Wagner

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.]

1. 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 (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 algorithms for other problems you might be more familiar with or might have heard of?

2. Let A and B be two search problems. Suppose you are told that A reduces to B (there is a polynomial-time reduction from A to B). Does it necessarily follow that B reduces to A (there is a polynomial-time reduction from B to A)? Briefly, why or why not?

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