I have been wondering a lot about a problem lately, that I believe has far reaching consequences.
Some context: There are many theoretical problems that are considered to be obviously far far outside our problem solving ability. Two examples of those would be the Collatz Conjecture and P vs NP.
My reasoning: If that’s the case, for each of those problems, there should be a strong knock-out argument for *why* they are intrinsically hard to solve.
My problem: I don’t know of any such argument.
If anyone knows any such knock-down argument for why those problems are so hard, I’d be very interested.
“Many smart researchers have tried solving them, and failed, and made no progress. This is why it is obvious that those problems are very hard.”
I understand this, but this does not help. It does not lead to a causal model for why those problems are hard. Let alone causal, it is not even a straightforward predictive model: to which extent people having failed at it inform that they will keep failing? You need some kind of model or informed prior to talk about that.
Even worse, it might entirely be tautological, where the definition of “hard” is something like “the amount to which we have tried to solve the problem and failed”.
It also fails to address the source of my confusion. When I try to describe it more precisely, it looks like “Given that so many geniuses have tried and failed, why don’t we have a solid explanation for why it doesn’t work?”
The shape of what I am looking for is something like a deep principle, a fundamental reason, or just a simple razor that explains how those problems fall outside the scope of what we know to solve
Phrased differently: it should be possible to define an over-approximation of what we can prove right now, and then show that those problems are not within this.
The more “far outside our problem solving ability” they are, the easier it should be to define this over-approximation and a razor to separate the problem from it.
“There are typical barriers to P vs NP described here (and many approaches in Scott Aaronson’s survey) or to the Collatz’s Conjecture”
I understand this, but after reading them, I am still confused. They are more along the line of “We have tried specific proof techniques and failed”, more than “they are super intractable”.
If you don’t make progress on a problem, a natural next best thing is usually to make progress on the meta-problem of “Why haven’t I made progress?”, in order to reflect about what went wrong.
As such, I have some meta-confusion that goes like “Is that question actually uninteresting at all, so much so that people do not study it? Or is it more that this question is also too hard to make any legible progress?”
“For any given difficult problem, you can walk up to an expert and ask them why it’s considered hard, but the answers they give you won’t have any unifying theme aside from that. It’s all ad hoc.”
Indeed, I expect that for each of those problems, there is some unifying reason that makes them hard. Or at most, a couple of general ones.
Experts from many different fields of Maths and CS have tried to tackle the Collatz’ Conjecture and the P vs NP problem. Most of them agree that those problems are way beyond what they set out to prove. And I mostly agree that each expert’s intuition vaguely tracks one specific dimension of the problem.
But any simplicity prior tells you that it is more likely for there to be a general reason for why those problems are hard along all those dimensions, rather than a whole bunch of ad-hoc reasons.
Many different approaches have been tried. In the case where only a couple of specific approaches have been tried, I expect the reason for why it hasn’t been solved to be ad-hoc and related to the specific approaches that have been tried. The more approaches are tried, the more I expect a general reason that applies to all those approaches.
Those problems are simple. In the case of a complicated problem, I would expect the reason for why it hasn’t been solved to be ad-hoc. I expect this much less in the case of simple problems.
Rewrote “Preemption #1”, it was not well explained enough.
Added “Preemption #3”, it was only implicit in the others, better to make it explicit.