Open problems often age poorly
With enough time and experience with research, you realize that most open problems are bad. In fact, for junior researchers, it might make sense to treat open problems as anti-advice: if you see a question posed as an open problem, that’s a good reason to not work on it.
Open problems have an important place for the junior researcher, though: solving them gives you clout. And if clout is the goal, the older the open problem is, the better. This is one reason why old open problems remain an important part of research. If your paper solves a 20-year-old open problem, then maybe it’s worth something.
I want to describe how I think about old open problems. Because I do think that older open problems tend to be more interesting than newer ones. But I think this is true for the same reason that old things tends to be better than new things: time filters out all but the best. Consequently, in the same way a song or a movie can age poorly, an open problem can age poorly too. And when, eventually, your priorities shift from carving out a place in the ivory tower to actually doing good research, you will need to figure out which old open problems are worth working on, and which are merely remnants of abandoned research programs.
How open problems are born
Researchers formulate open problems for different reasons. Ignoring the purely self-interested reasons (We want follow-up papers to our work; we got sucked down a month-long rabbit hole trying to get the tightest version of Lemma 28, and are desperate to find someone else to vent to about it), there’s two broad classes of reasons.
Some open problems are interesting because they identify gaps in our understanding, and therefore act as a reasonable “next step” for a research program: (This problem is so natural that we believe an answer would be the start of a larger theory.)
- Our technical toolkit in this area is not strong enough to prove our dream result; here is a candidate first step to getting to the dream.
- This question is so fundamental to our body of work that it is embarrassing that we don’t know the answer. (Invariant subspace conjecture)
Some open problems are interesting because they imply interesting consequences (or they are so natural that they must have interesting applications).
- This conjecture would imply something really cool. (Matrix multiplication exponent)
- This conjecture is the natural culmination of a long line of theorems. (Schinzel’s hypothesis H
One way to think about these two types are that they are interesting because they are either the “first word” or the “last word” on a topic.
It’s a good exercise to think about what the open problems you see in papers are for. If a paper gives an algorithm for a problem which runs in $O(n^2 \operatorname{polylog}(n))$ time, and the authors ask whether the polylog term can be removed, what is that for? Is the hope that a cleaner proof is out there? A simpler algorithm? A more practical algorithm?
How open problems age
Open problems aren’t impervious to age. As the research community develops, consensus changes, and priorities shift, it may turn out that open problems may have an intention that we see now was misguided or unfruitful.
When these open problems are young, they could be confused for the kind of problem which just requires a clever new insight, an insight with enough brevity and clarity that it could carry to other related problems. However, as they age, it’s revealed that, in fact, the community can move on without it, can develop techniques to handle most of the problems it’s interested in, and that this open problem is an anomaly which does not signal lack of understanding, but rather, signals a lack of interesting mathematical structure. Some problems should be dissolved instead of solved. If a question is too hard, it may be the wrong question to ask.
Example 1
A recent example I heard is that of oracle separations. This is a common type of result in computational complexity which has its roots in the older days of complexity theory: we want to prove that class A and class B are not equal. We can’t prove this in the real world, but maybe we can prove them in the “relativized world”, aka relative to an oracle. This has roots in a time where thinking about classes relative to an oracle was seen as a “toy version” or a way to get at the intricacies of the real-world complexity classes. Consequently there are quite old open problems which ask for an oracle separation between two complexity classes.
The prevailing winds of complexity theory have worked to chip away at the significance of the oracle separation. For one, an oracle separation between two classes does not necessarily say anything about whether the two classes are equal in the real world. For example, one of the gems of complexity theory is that IP = PSPACE, but this proof works despite IP being unequal to PSPACE relative to a random oracle. What it does mean is that there is that it rules out “relativizing” proofs that they are equal. However, for any sufficiently interesting separation question, we already believe that the proof has to be non-relativizing. So, it’s generally quite difficult to evaluate whether any given oracle separation is interesting, even for experts in theoretical computer science. I definitely don’t know which ones are interesting.
In sum, with an oracle separation comes a promise of insight: if we show a separation relative to an oracle, maybe this provides evidence for that separation in the real world, or at least provides some insight into the real world classes. However, complexity classes are broadly so complicated that not even the experts can do this, unless they deeply understand how the proofs of these oracle separations work. Oracle separations present themselves as the “first step” towards bigger results, but this is mostly a mirage.
Example 2
Open problems can also age poorly when their infamy outlives their research context. Some examples might include the existence of mutually unbiased bases/SIC-POVMs in every dimension, the [evasiveness conjecture](evasiveness conjecture), and the log-rank conjecture. These questions have cachet within their respective communities because they are relatively easy to state, and yet have under-appreciated difficulty. If you dig into the surrounding literature, though, you might come to the conclusion that they were posed for reasons that are not that interesting today. This might be because we already know partial results which satisfies us; it might be motivated by research dreams which did not pan out; or it might be a question whose difficulty suggests that it is the wrong question to ask.
For example, consider the 1/3-2/3 conjecture; the reason that this was posed is because it controls the number of comparisons needed to sort $n$ items. However, suppose you actually cared about this sorting question. Then we already know weaker versions of the conjecture, which gets the right number of comparisons up to a constant factor. And if we care about the constant, then the question posed by the 1/3-2/3 conjecture is not actually the right approach; it’s been conjectured that the correct constant is slightly smaller than this gets, since you don’t expect the worst possible poset in every iteration.
This is a very common flavor of open problem you see in open problem lists: they are open problems, not because they strongly hinder our understanding, but because mathematicians in the field, when rummaging around for pretty results, found an unusually difficult problem in an unexpected place. And, well, if the only remarkable thing about the problem is its difficulty, why work on it? If you change the problem slightly, you find a beautiful result with a short proof; if you are okay with a weaker answer, you again get a beautiful result with a short proof.
Evaluating open problems
It’s easy to find reasons to not work on open problems. The cranky professor’s favorite pasttime is to explain why that recently proved conjecture is actually overrated. However, it’s important to think about this stuff if you are going to think about the “metagame” of research. Open problems are beacons in the community. They are attention sinks. If you want to work on one, are you sure you’re well-positioned to do so? Do you understand why it’s hard? Do you think you have something that other people don’t, whether that be modern techniques, motivation, or an outsider perspective? Or do you simply believe that working on it will surely admit an interesting result, even if you odn’t resolve it outright?
When you develop those skills, you can begin to question the dogma that was taught to you at the start of your career. Is P versus NP worth working on, or even worthwhile as a north star? What would we learn from resolving the global regularity of Navier-Stokes? Is the Aaronson-Ambainis conjecture interesting as a quantum computing question or a boolean analysis question (or neither)?
And you can also start to notice when your mind changes on a problem. That finite automata question looked boring until it was linked to trace reconstruction. Oh, that chromatic number formulation of the log-rank conjecture looks a lot more natural than the standard one.