Why are some problems Super Hard?
Because there's a long chain of undiscovered abstractions between the abstractions we have now and the abstractions needed to solve such problems. Or, equivalently, writing down/conceptualizing the solution in terms of extant abstractions would result in a solution too long to fit in a human's working memory.
To elaborate: At any given time, we have a number of extant conceptual tools/building blocks. Proven math theorems, established mathematical frameworks, discovered laws of physics, other ideas. We can put these conceptual blocks together to create new tools/blocks, like defining a new mathematical function in terms of some other functions. We then abstract over the result: learn to think of the new function as its own thing that has its own rules/properties, without explicitly thinking about its definition. We chunk our understanding.
Human working memory is limited. We can effectively consider situations only of limited mental complexity, can fit only so much under our mind's eye. Past a certain point, we have to factorize, break the problem down into sub-problems.
Chunking is part of that. If solving some problem requires putting together 20 conceptual building blocks, we can divide them into five groups, abstract over every four-piece group, and then reason about the five higher-level building blocks. Each of these blocks would be "equivalent" to the four blocks they're made of, in the context of this specific problem, but their mental complexity will have been reduced to the higher-level summary of the four-block system.
As such, for any given pair of , there's some length that denotes the shortest solution to the research problem expressed in terms of the extant conceptual tools. If is larger than a human's working-memory capacity , then the problem would need to be broken down into sub-problems before it can be solved. Specifically, it'd need to be broken down times.
And if that value is very large, the problem is Super Hard: we'd need to do a lot of conceptual engineering before we can reason out the solution. Build a "conceptual bridge" to it.
Analogies:
Any reason to expect that P vs NP or the Collatz Conjecture in particular have unusually long undiscovered abstraction-chains? (Other than nobody having solved them already.) What's the feature of these particular problems which makes them particularly difficult?
Because there’s a long chain of undiscovered abstractions between the abstractions we have now and the abstractions needed to solve such problems
If there's a guaranteed sequential , non acyclic, stack of abstractions, with just a few missing, you're playing on easy mode.
Philosophical problems are hard because of circularities...we don't know which of logic, epistemology, ontology, etc, is for fundamental....and can't figure it out without establishing a starting point.
I agree this establishes that the Collatz' and P vs NP Conjectures have longer chain length than everything that has been tried yet. But this looks to me like a restatement of "They are unsolved yet".
Namely, this does not establish any cause for them being much harder than other merely unsolved yet problems. I do not see how your model predicts that the Collatz' and P vs NP Conjectures are much harder than other theorems in their fields that have been proved in the last 15 years, which I believe other experts have expected.
Put differently, the way I unders...
A better approach to answering why a specific problem is super-hard given a certain level of knowledge is doing a post-mortem on hard-but-solved problems. A few random examples:
One could ask the following questions, one easy and one hard:
Once/if you answer these, and figure out some patterns of hardness, you can then think about yet-unsolved problems and see if you can spot the same signs. If you are lucky, it might also give you promising directions for fruitful research.
Edit: it may well be that there is no recognizable pattern, some peaks are taller than others but all are hidden in the clouds and the only way to find out is through the hard work of climbing them.
Interesting.
A nice way to do such a post-mortem would be to actually ask the people who were there if they thought the problem was Super Hard, why so, and how they did update after the solution was found.
Thanks!
My intuition is that both P vs NP and Collatz are hard for a similar reason: they're asking about arbitrary problems, without any interesting special structure.
The vast majority of our math is developed to handle problems with some special structure - symmetry, linearity, locality, etc. P vs NP is asking "ok, but how hard is it to solve arbitrary problems without any special structure, other than the ability to check a solution efficiently?". And Collatz is just a random-ass problem which doesn't seem to have any special structure to it.
If we want to make progress on arbitrary problems without any special structure, then we need insights into problem-solving in general, not just the myriad of special cases which we usually think about. Our insights need to be maximally generalizable, in some sense. In the case of Collatz, there might exist some special trick for it, but it's not any of the tricks we know. In the case of P vs NP, the problem itself is directly about very general problem-solving.
And Collatz is just a random-ass problem which doesn't seem to have any special structure to it.
The Collatz Conjecture has a lot of structure to it:
In the case of Collatz, there might exist some special trick for it, but it's not any of the tricks we know.
I am not sure what you counts o...
I disagree. Any given arbitrary problem is an instance of some broader set of problems, such that knowing how to solve that arbitrary problem allows you to trivially solve any other problem in that broader set. Conversely, if you can't trivially solve it, that means you don't understand the entirety of some fairly broad segment of concept-space.
In that sense, there's no problems "without any interesting special structure" that are hard to solve relative to some conceptual toolbox. If you can't trivially solve it, there are interesting structures to be unco...
Consider this problem: Are there are an infinite number of 9s in the digits of pi? The answer is obviously yes. The only way it could be no is if pi interacts in some strange way with base-10 representations, and pi has nothing to do with base-10.
But how do you prove that no such interaction exists? You have to rule out an endless number of possible interactions, and even then there could be some grand conspiracy between pi and base-10, hiding in the places you haven't yet looked.
Proving the absense of an interaction between two areas of math is much harder than proving its presence. If you want to prove presence, you can just find the interaction and explain it. But you can't "find an absence."
Most of the hard math problems turn out to have this issue at their core. If you dig into Collatz, you find that it's very likely to be true. The only way it could be false is if there's an undiscovered conspiracy between parities of integers and the collatz map. How to prove there is no conspiracy?
Aren't proofs by contradiction the standard technique for proving the absence of a property.
You can prove ¬P by proving that P => FALSE?
With regards to P Vs NP, I think it's relevant that the vast majority of interesting questions in complexity theory are open, despite this being an area which has received a lot of attention in the last 50 years. This suggests that it's hard to solve this problem because we haven't come up with good techniques in this field - it's like trying to climb Everest using 15th century technology.
There is a class of super-hard problems (AI alignment, a lot of social change) which are hard because they're adversarial (at least partly). If different agents value different results, there can be no single preferred outcome (there may be a negotiated agreeable outcome, or there may not, but it won't be "best" for everyone).
I don't think that's what you're talking about though. I think part of the explanation is that we don't have a model for distance from success. We have no clue if the researchers who've made serious attempts on these problems got us closer to an answer/proof, or if they just spun their wheels. In other words, these problems are hard because we haven't found an incremental way to solve them.
Note that this is related to the reasons that colonizing Mars or mining asteroids is hard - there's a lot of problems that need to be solved, many of which we don't know a feasible/economical approach to, and as long as any of them is unsolved, the end-result remains impossible. Also similarly, there are discoveries about the sub-problems that are valuable in themselves, even if they don't get us to the stated goal.
I think part of the explanation is that we don't have a model for distance from success. We have no clue if the researchers who've made serious attempts on these problems got us closer to an answer/proof, or if they just spun their wheels.
This post is about experts in the fields of number theory and complexity theory claiming to have a clue about this.
If you think "We have no clue", you likely think they are wrong, and I would be interested in knowing why.
I added more details on this comment, given that someone else already shared a similar thought
For those two problems in particular, there are good reasons to expect them to be difficult to solve.
There are lots of Collatz-like problems that are formally undecidable, in the sense that for any formal system there exists a similar iteration problem where the formal system cannot prove the behaviour one way or the other. It is plausible that the actual Collatz system is one of these for our standard proof systems, and that the answer depends upon what we actually mean by natural numbers in some stronger sense.
P vs NP is another candidate for an undecidable problem, dealing as it does with general behaviour of Turing machines that can run programs with rather weak bounds. There's a lot that we can't yet prove about about general computation systems, and we have theorems that say we should expect there to be a lot that we can't ever prove. It would be unsurprising if quite a lot of the problems we can't solve after trying very hard are actually not solvable.
It is plausible that the actual Collatz system is one of these for our standard proof systems.
Why? Consider the following:
The Collatz Conjecture has a lot of structure to it:
- It is false for 3n-1
- It is undecidable for generalizations of it
- It is true empirically, up to 10^20
- It is true statistically, a result of Terrence Tao establishes that "almost all initial values of n eventually iterate to less than log(log(log(log(n))))" (or inverse Ackermann)
Additionally, if you look at the undecidable generalizations of the Collatz Conjecture, I expect that you will fi...
There are a lot of Super Hard problems where we do know why they are hard to solve. Quite a few of them in fact:
- How can we cure cancer?
- How can we maintain human biological hardware indefinitely?
- How can we build a human traversible wormhole?
- How can we build a dyson sphere?
- How can societies escape inadequate equilibria?
Are these perhaps boring, because the difficulty is well understood?
Would it be worthwhile to enumerate the various classes of Super Hard problems, to see if there are commonalities between them?
Are these perhaps boring, because the difficulty is well understood?
They are not boring, I am simply asking about some specific cluster of problems, and none of them belong to that cluster.
One alternative to problems being super hard would be if we had some algorithm running in some reasonable amount of time, say, polynomial time, which could solve them. But proving mathematical statements is NP-complete, so such an algorithm would show that P=NP, while a proof that such an algorithm cannot exist would show that P != NP.
Why is proving mathematical statements NP-complete? There is no guarantee that a polynomial length proof of a true mathematical statement of length N exists.
Here’s one candidate reason for P vs NP: the hard instances of any NPC problem are often the same as the hard instances of any other NPC problem, including a (yet to be formalized) problem that will turn equivalent to proving P vs NP. Then, it’s hard to prove almost by definition.
The problem
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.
Preemption #1
"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.
Preemption #2
"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?"
Preemption #3
"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.
Restated:
Edits