My previous entries were mostly about the applications of my line of research to text classification, but for me as an individual, the problems that we study in theoretical computer science have more immediate advantages. One is that boredom is a thing of the past. When I find myself waiting for the bus or in a meandering queue, I rummage through my internal box of things that needs to be figured out, and select something juicy. Then, I simply nestle up inside my own thoughts and let the world go about its business without me.
A good portable problem has a compact definition, and sits in the middle of some area which I am reasonably familiar with. However, and most importantly, the problem should seem easy but have resisted all attacks so far. I suspect that many feel this way about Goldbach's conjecture, stating that every even integer greater than 2 can be written as the sum of two primes. Goldbach wrote to Euler that he “regards this as a completely certain theorem, although I [he] cannot prove it.” This was in 1742, and even to today’s date, neither he nor anyone else has come up with a proof, despite intense efforts and a promised 1 million dollar award.
Another good use for that box of problems is falling asleep. I have one graph partitioning problem that is so complicated that my brain basically gives me a blue screen whenever I start thinking about it. When I first picked it up, I really wanted a solution, but now I suspect that the problem has greater value for me unsolved. Perhaps 2014’s Christmas gift is a quality problem. They leave your bank account unscathed, are easy to package, have no carbon footprint to speak of, and even though you give them away, you still get to keep them.
Blog post written by Johanna Björklund, CTO, for Umeå University's "Forskarbloggen" (the Reasearcher Blog).