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 (conceptual toolbox,research problem), there’s some length L that denotes the shortest solution to the research problem expressed in terms of the extant conceptual tools. If L is larger than a human’s working-memory capacity M, 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 ⌈logML⌉−1 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:
Manufacturing. To build the most advanced of the modern technologies, there’s a long line of tools-building-tools-building-....-tools-building-tools, if we’re starting from the Stone Age tech.
Programming. It’s often advised to break down long functions into sub-functions of less than five or less than ten lines, otherwise they’re pretty hard to think about and bugfix.
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?
My instinctive answer is that no, there’s no special property, no neat compact reason. It just so happens that these specific pairings of (conceptual toolbox,research problem) have a very large L. If we were a different or alien culture, that has historically pursued different branches of math and started from different native concepts, these problems might’ve been trivial, and some of our trivial problems might’ve been tremendously difficult.
I guess “what native concepts we start with” and therefore “what math branches we historically pursue” might not be entirely arbitrary, conditioning on the fact that we’re evolved life. There might even be some generalities across most probable instances of naturally-evolved minds. But that’s the only source of non-arbitrariness I see here.
A starker example is the Fermat’s Last Theorem. There’s really no reason I can see why it “had” to have a proof over 100 pages long. (Also, this is why I think Fermat was full of it when he claimed to have solved it. I’m sure mathematicians following him have cycled through all possible math-tools of his time and their neighborhoods, so unless he built a really long chain of math results in his private time and then published none of it, he couldn’t have done it.)
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.
Well, yes, if you can’t conceptualize the solution because it’s too large, you don’t know what building blocks go into it, and you don’t even necessarily know in which direction to build the bridge/what frameworks to develop/what sub-problems to solve. Indeed, that’s probably where most of the difficulty lies, especially in pre-paradigmic fields.
It’s even more stark if we view it in terms of individual researchers, and not the entire civilization. Any given human has access to only a subset of the conceptual toolbox of the civilization, and if some problem in Domain A can be solved by a tool from a distinct Domain B, it might be a long time before a specialist with knowledge of both comes around; or alternatively, before Domain A people re-invent the relevant tool already present in Domain B.
Still, this sort of cross-domain bleed-through is more of a “low-hanging fruit”, in the sense that if a problem is very famous, most of our civilization’s tools have already been tried on it, in every combination that makes sense. The bottleneck then is genuine conceptual engineering.
Well, yes, if you can’t conceptualize the solution because it’s too large,
It might be to big for a brain, but it also might be inherently circular. (A closed loop can be small) How would you know which? What guarantee do you have that it’s a stack of abstractions?
Remember, all forms of engineering are easy mode compare to science, which is easy compared to philosophy.
The bottleneck then is genuine conceptual engineering.
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 understand it, your model explains things post-hoc (ie, “if some problems are not solved, then, they must have had long chains”), but does not make predictions (how long do you expect their chains to be? how does this translate in terms of difficulty?).
The post is about predictions made by experts in number theory and complexity theory.
If you think that this can not be predicted, and that they are thus wrong about their predictions, I would be interested in knowing why.
Namely:
Do you have mechanistic / gear-level / inside view reasons for why the difficulty of problems can not be predicted ahead of time, where you disagree with those experts?
Do you have empirical / outside view reasons for why those experts are badly calibrated?
The post is about predictions made by experts in number theory and complexity theory.
Isn’t it about empirical evidence that these problems are hard, not “predictions”? They’re considered hard because many people have tried to solve them for a long time and failed, not because experts glanced at them once and knew on priors they’d be legendarily difficult.
Aside from that, an expert can estimate how hard a problem is by eyeballing how distant the abstractions needed to solve it feel from the known ones — whether we have almost the right tools for solving it, or have no idea how the right tools would look at all. They’re able to do this because they’ve developed strong intuitions for their professional domain: they roughly know what’s possible, what’s on the edge of the possible, and what’s very much not. And even then, such intuitions are often very wrong, see Fermat’s Last Theorem.
But there’s no objective property that makes these problems intrinsically hard, only subjectively hard from the point of view of our conceptual toolbox.
Isn’t it about empirical evidence that these problems are hard, not “predictions”? They’re considered hard because many people have tried to solve them for a long time and failed.
No, this is Preemption 1 in the Original Post.
“hard” doesn’t mean “people have tried and failed”, and you can only witness the latter after the fact. If you prefer, even if have empirical evidence for the problem being “level n hard” (people have tried up to level n), you;d still do not have empirical evidence for the problem being “level n+1 hard” (you’d need people to try more to state that if there’s nothing you can say about it ahead of time). Ie, no predictive power.
An expert can estimate how hard a problem is by eyeballing how distant the abstractions needed to solve it feel from the known ones
Great! We’re getting closer to what I care about.
Then what I am saying is that there is a heuristic that the experts are using to eyeball this, and I want to know what that is, start ingwith those 2 conjectures!
I am also saying that the more distant “the abstraction need to solve it feel from the known ones”, the easier it should be to do so.
They’re able to do this because they’ve developed strong intuitions for their professional domain: they roughly know what’s possible, what’s on the edge of the possible, and what’s very much not.
Exactly, but those intuitions are implemented somehow. How?
Also, the more experts agree on a judgment, and the stronger their judgment, the easier you expect to be to explain that intuition.
But there’s no objective property that makes these problems intrinsically hard, only subjectively hard from the point of view of our conceptual toolbox.
I was confused very confused when I read this. For instance, the part in bold is already reflected in the Original Post.
There are many theoretical problems that are considered to be obviously far far outside our problem solving ability.
If you prefer, interpret “intrinsically hard” as “having an intrinsic property that makes it subjectively hard for us. To model how that would look, consider the following setup:
The space of problems is just the real plane, and our ability to solve problems is modeled by a unit disk in the plane (if in the disk, solved, and the closer it is to the disk, the easier it is to solve). Then, the difficulty of a problem is subjective, it depends on where the disk is.
But let’s say the disk is somewhere on the x axis, then the intrinsic property of a problem being far having a high y coordinate, makes it subjectively hard.
I’ll make some edits to the post. I thought most of this was clear because of Preemption #1, but it was not.
even if have empirical evidence for the problem being “level n hard” (people have tried up to level n), you;d still do not have empirical evidence for the problem being “level n+1 hard”
This is implicitly assuming that our expectation of how long a problem should take to solve is memoryless. But a breakthrough is much more likely on the 1st day of working on a problem than on the 1000th day. More generally, if problems vary greatly in difficulty, then our failure to solve a given problem provides evidence that it’s one of the harder problems. So a more reasonable prior in this case is something like logarithmic—e.g. it’s equally likely that a problem takes 1-10 days, or 10-100 days, or 100-1000 days, etc, to solve.
A similar model can give rise to the Lindy effect, where the expected lifetime is proportional to the lifetime so far. (In this case it’d be the expected time to solving the problem which would be proportional to the time which the problem has been open.)
even if have empirical evidence for the problem being “level n hard” (people have tried up to level n), you;d still do not have empirical evidence for the problem being “level n+1 hard” (you’d need people to try more to state that if there’s nothing you can say about it ahead of time). Ie, no predictive power.
Suppose I take out a coin and flip it 100 times in front of your eyes, and it lands heads every time. Will you have no ability to predict how it lands the next 30 times? Will you need some special domain knowledge of coin aerodynamics to predict this?
Then what I am saying is that there is a heuristic that the experts are using to eyeball this, and I want to know what that is, start ingwith those 2 conjectures!
I mean… That heuristic is that heuristic? “Experts have a precise model of the known subset of the concept-space of their domain, and they can make vague high-level extrapolations on how that domain looks outside the known subset, and where in the wider domain various unsolved problems are located, and how distant they are from the known domain”. The way I see it, that’s it. This statement isn’t reducible to something more neat and simple. 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.
Why would you think there’s something else? What shape do you want the answer to have?
Suppose I take out a coin and flip it 100 times in front of your eyes, and it lands heads every time. Will you have no ability to predict how it lands the next 30 times? Will you need some special domain knowledge of coin aerodynamics to predict this?
Coin = problem
Flipping head = not being solved
Flipping tail = being solved
More flips = more time passing
Then, yes. Because you had many other coins that had started flipping tail at some point, and there is no easily discernable pattern.
By your interpretation, the Solomonoff induced prior for that coin is basically “it will never flip tail”. Whereas, you do expect that most problems that have not been solved now will be solved at some point, which does mean that you are incorporating more knowledge.
“Experts have a precise model of the known subset of the concept-space of their domain, and they can make vague high-level extrapolations on how that domain looks outside the known subset, and where in the wider domain various unsolved problems are located, and how distant they are from the known domain”
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. I mostly agree with you on the fact 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.
The way I see it, that’s it. This statement isn’t reducible to something more neat and simple.
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.
What makes you think that? I see you repeating this, but I don’t see why that would be the case.
Why would you think there’s something else?
Good question, thanks! I tried to hint at this in the Original Post, but I think I should have been more explicit. I will make a second edit that incorporates the following.
The first reason is that 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.
The second reason is that the 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 have much less of this expectation for simple problems.
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 (conceptual toolbox,research problem), there’s some length L that denotes the shortest solution to the research problem expressed in terms of the extant conceptual tools. If L is larger than a human’s working-memory capacity M, 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 ⌈logML⌉−1 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:
Manufacturing. To build the most advanced of the modern technologies, there’s a long line of tools-building-tools-building-....-tools-building-tools, if we’re starting from the Stone Age tech.
Programming. It’s often advised to break down long functions into sub-functions of less than five or less than ten lines, otherwise they’re pretty hard to think about and bugfix.
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?
My instinctive answer is that no, there’s no special property, no neat compact reason. It just so happens that these specific pairings of (conceptual toolbox,research problem) have a very large L. If we were a different or alien culture, that has historically pursued different branches of math and started from different native concepts, these problems might’ve been trivial, and some of our trivial problems might’ve been tremendously difficult.
I guess “what native concepts we start with” and therefore “what math branches we historically pursue” might not be entirely arbitrary, conditioning on the fact that we’re evolved life. There might even be some generalities across most probable instances of naturally-evolved minds. But that’s the only source of non-arbitrariness I see here.
A starker example is the Fermat’s Last Theorem. There’s really no reason I can see why it “had” to have a proof over 100 pages long. (Also, this is why I think Fermat was full of it when he claimed to have solved it. I’m sure mathematicians following him have cycled through all possible math-tools of his time and their neighborhoods, so unless he built a really long chain of math results in his private time and then published none of it, he couldn’t have done it.)
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.
Well, yes, if you can’t conceptualize the solution because it’s too large, you don’t know what building blocks go into it, and you don’t even necessarily know in which direction to build the bridge/what frameworks to develop/what sub-problems to solve. Indeed, that’s probably where most of the difficulty lies, especially in pre-paradigmic fields.
It’s even more stark if we view it in terms of individual researchers, and not the entire civilization. Any given human has access to only a subset of the conceptual toolbox of the civilization, and if some problem in Domain A can be solved by a tool from a distinct Domain B, it might be a long time before a specialist with knowledge of both comes around; or alternatively, before Domain A people re-invent the relevant tool already present in Domain B.
Still, this sort of cross-domain bleed-through is more of a “low-hanging fruit”, in the sense that if a problem is very famous, most of our civilization’s tools have already been tried on it, in every combination that makes sense. The bottleneck then is genuine conceptual engineering.
It might be to big for a brain, but it also might be inherently circular. (A closed loop can be small) How would you know which? What guarantee do you have that it’s a stack of abstractions?
Remember, all forms of engineering are easy mode compare to science, which is easy compared to philosophy.
Unless it’s circularity.
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 understand it, your model explains things post-hoc (ie, “if some problems are not solved, then, they must have had long chains”), but does not make predictions (how long do you expect their chains to be? how does this translate in terms of difficulty?).
I don’t think this can be predicted.
The post is about predictions made by experts in number theory and complexity theory.
If you think that this can not be predicted, and that they are thus wrong about their predictions, I would be interested in knowing why.
Namely:
Do you have mechanistic / gear-level / inside view reasons for why the difficulty of problems can not be predicted ahead of time, where you disagree with those experts?
Do you have empirical / outside view reasons for why those experts are badly calibrated?
Isn’t it about empirical evidence that these problems are hard, not “predictions”? They’re considered hard because many people have tried to solve them for a long time and failed, not because experts glanced at them once and knew on priors they’d be legendarily difficult.
Aside from that, an expert can estimate how hard a problem is by eyeballing how distant the abstractions needed to solve it feel from the known ones — whether we have almost the right tools for solving it, or have no idea how the right tools would look at all. They’re able to do this because they’ve developed strong intuitions for their professional domain: they roughly know what’s possible, what’s on the edge of the possible, and what’s very much not. And even then, such intuitions are often very wrong, see Fermat’s Last Theorem.
But there’s no objective property that makes these problems intrinsically hard, only subjectively hard from the point of view of our conceptual toolbox.
No, this is Preemption 1 in the Original Post.
“hard” doesn’t mean “people have tried and failed”, and you can only witness the latter after the fact. If you prefer, even if have empirical evidence for the problem being “level n hard” (people have tried up to level n), you;d still do not have empirical evidence for the problem being “level n+1 hard” (you’d need people to try more to state that if there’s nothing you can say about it ahead of time). Ie, no predictive power.
Great! We’re getting closer to what I care about.
Then what I am saying is that there is a heuristic that the experts are using to eyeball this, and I want to know what that is, start ingwith those 2 conjectures!
I am also saying that the more distant “the abstraction need to solve it feel from the known ones”, the easier it should be to do so.
Exactly, but those intuitions are implemented somehow. How?
Also, the more experts agree on a judgment, and the stronger their judgment, the easier you expect to be to explain that intuition.
I was confused very confused when I read this. For instance, the part in bold is already reflected in the Original Post.
If you prefer, interpret “intrinsically hard” as “having an intrinsic property that makes it subjectively hard for us. To model how that would look, consider the following setup:
The space of problems is just the real plane, and our ability to solve problems is modeled by a unit disk in the plane (if in the disk, solved, and the closer it is to the disk, the easier it is to solve). Then, the difficulty of a problem is subjective, it depends on where the disk is.
But let’s say the disk is somewhere on the x axis, then the intrinsic property of a problem being far having a high y coordinate, makes it subjectively hard.
I’ll make some edits to the post. I thought most of this was clear because of Preemption #1, but it was not.
This is implicitly assuming that our expectation of how long a problem should take to solve is memoryless. But a breakthrough is much more likely on the 1st day of working on a problem than on the 1000th day. More generally, if problems vary greatly in difficulty, then our failure to solve a given problem provides evidence that it’s one of the harder problems. So a more reasonable prior in this case is something like logarithmic—e.g. it’s equally likely that a problem takes 1-10 days, or 10-100 days, or 100-1000 days, etc, to solve.
A similar model can give rise to the Lindy effect, where the expected lifetime is proportional to the lifetime so far. (In this case it’d be the expected time to solving the problem which would be proportional to the time which the problem has been open.)
Suppose I take out a coin and flip it 100 times in front of your eyes, and it lands heads every time. Will you have no ability to predict how it lands the next 30 times? Will you need some special domain knowledge of coin aerodynamics to predict this?
I mean… That heuristic is that heuristic? “Experts have a precise model of the known subset of the concept-space of their domain, and they can make vague high-level extrapolations on how that domain looks outside the known subset, and where in the wider domain various unsolved problems are located, and how distant they are from the known domain”. The way I see it, that’s it. This statement isn’t reducible to something more neat and simple. 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.
Why would you think there’s something else? What shape do you want the answer to have?
Coin = problem
Flipping head = not being solved
Flipping tail = being solved
More flips = more time passing
Then, yes. Because you had many other coins that had started flipping tail at some point, and there is no easily discernable pattern.
By your interpretation, the Solomonoff induced prior for that coin is basically “it will never flip tail”. Whereas, you do expect that most problems that have not been solved now will be solved at some point, which does mean that you are incorporating more knowledge.
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. I mostly agree with you on the fact 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.
What makes you think that? I see you repeating this, but I don’t see why that would be the case.
Good question, thanks! I tried to hint at this in the Original Post, but I think I should have been more explicit. I will make a second edit that incorporates the following.
The first reason is that 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.
The second reason is that the 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 have much less of this expectation for simple problems.