Manuel Blum generally has one open* problem on his exams. Manuel Blum was one of the best teachers I ever had (he taught complexity theory at Berkeley—he’s at CMU now). It is possible to get 1000 out of 100 on his exams, apparently.
In the sense of “no one bothered writing it up, but generally you should be able to do it in a timed setting if you thought about a class problem in depth as is encouraged but not required.”
Consider that if a somewhat “out of the left field” problem is on the exam, it is there to separate the upper end of the curve. One could imagine some reasons a professor might want to do that.
Speaking as a former algorithms-and-complexity TA --
Proving something is in NP is usually trivial, but probably would be worth a point or two. The people taking complexity at a top-tier school have generally mastered the art of partial credit and know to write down anything plausibly relevant that occurs to them.
I think roystgnr’s comment was meant to be parsed as:
“Hmm… I can prove that this is in NP, and I can prove it is not in P and is not in NP-Complete. But that’s not worth any points at all!” (crumples up and throws away paper)
Corollary:
...they shouldn’t have crumpled that piece of paper.
Manuel Blum generally has one open* problem on his exams. Manuel Blum was one of the best teachers I ever had (he taught complexity theory at Berkeley—he’s at CMU now). It is possible to get 1000 out of 100 on his exams, apparently.
In the sense of “no one bothered writing it up, but generally you should be able to do it in a timed setting if you thought about a class problem in depth as is encouraged but not required.”
Consider that if a somewhat “out of the left field” problem is on the exam, it is there to separate the upper end of the curve. One could imagine some reasons a professor might want to do that.
“Write a polynomial-time algorithm for X, or prove X is NP-Complete. For extra credit, do both.”
“Hmm… I can prove that this is in NP, but not in P or in NP-Complete. That’s not worth any points at all!” (crumples up and throws away paper)
Speaking as a former algorithms-and-complexity TA --
Proving something is in NP is usually trivial, but probably would be worth a point or two. The people taking complexity at a top-tier school have generally mastered the art of partial credit and know to write down anything plausibly relevant that occurs to them.
I think roystgnr’s comment was meant to be parsed as:
Corollary:
...they shouldn’t have crumpled that piece of paper.
That was my intention; thanks for fixing the phrasing.