We all like problems. But it's sort of sad that as our careers develop, we get to spend less and less time on problems that don't offer opportunities for resume enhancement. I don't think twice about watching a 3-hour movie, but feel guilty if I spend more than an hour on a problem that has nothing to do with research...
A fellow grad student was TAing an algorithms class and posed a question about the change-making problem. In the change-making problem, you're given a set of denominations c1 > c2 > ... > cN and a value M and asked to find the minimum number of coins that add up to M. The greedy strategy is to choose as many c1's as possible, then as many c2's as possible etc. Is there a polynomial-time algorithm that, given a set of denominations as input, tells if the greedy strategy is always optimal for the set (i.e., optimal for every M)?
We pondered awhile, but then of course I had to ruin things by Googling the very elegant solution published by David Pearson a decade back.
Fresh-faced undergrads and first-year grads out there, resist the urge. Enjoy your freedom and treat each problem the same while you still can, before your research becomes too compelling (= compulsory)
I AGREE that fresh-faced undergrads (are there such things)
ReplyDeleteand first-year grads should work on problems and not look at
the web for answers.
BUT even Full and Senile profs benefit from looking at problems.
MANY times a `fun' problem can lead to `serious' research.
The border between `fun' and `serious' is at times artificial
anyway.
Recently looking at an old INTERNATIONAL OLYMPIAD problem
let me to several research problems and some papers now
in the works.
And of course the `fun' problem of the Konisgburgh bridges
lead to the invention of graph theory.
There are other examples.
Yes, Bill, it's nice when that happens - one encounters a problem accidentally, and it leads to a full-fledged research program. But maybe it's more and more true that the contexts in which problems arise are established resesearch areas, especially in complexity proper, which in one way is an indication of the maturity of the field. I know a theorist who doesn't like to discuss any problem which isn't related to his program for separating P from NP, but this is admittedly an extreme case.
ReplyDeleteSorry, forgot to sign that last comment.
ReplyDeleteRahul.