I generally agree that computational complexity is probably relevant to the problem of AGI, but I can see several problems in your arguments:
There are several arguments the AGI problem is of a similar “flavor” to problems that are NP-complete.
Many proposed AI algorithms solve problems which are NP-hard (or worse, PSPACE-hard) in the general case. Keep in mind however, that NP-hardness and related notions are part of worst-case complexity theory, while average-complexity w.r.t. some appropriate class of “natural” problem distributions is relevant for AI and AGI. The relationship between worst-case complexity and average-complexity is poorly understood in the general case, and what would constitute a “natural” problem distribution is even less understood.
Similarly, Goedel incompleteness means there is no single algorithm for proving all provable theorems.
No. You can prove all provable theorems by just enumerating and checking all candidate proofs. Gödel’s incompleteness theorem states that there are certain statements which are “true” (in a suitable technical sense which intuitively boils down to the fact that you will never be able to find a counterexample) but are unprovable, unless arithmetic in inconsistent.
It feels like there is a principle of mathematics which rules out algorithms that are “too good to be true”: a single “magic wand” to solve all problems. In a similar way, AGI is a “magic wand”: it solves “all” problems because you can simply delegate them to the AGI.
It can be true that “magic wand” algorithms can’t exist because of complexity issues, but this would not be an issue for a humal-level AGI since humans aren’t “magic wands”. A strongly super-human AGI would be much more like a “magic wand” and I would agree that the theoretical and practical possibility of this kind of intelligence is much more speculative.
Another argument has to do with Solomonoff induction.
I think that Solomonoff induction and the intelligence metrics based on it, even with the inclusion of resource penalties a la Levin complexity, are too strong and don’t accurately capture the notion of effectively physically realizable intelligence.
Consider the bit sequence generated by a strong stream chiper with an (uniformly sampled) key. It has a very small Levin complexity, but, as per the one-way function conjecture we don’t expect any AI to be ever able to efficiently predict it, as it would amount to breaking the chiper. And yet, according to intelligence metrics based on Kolmogorov or Levin complexity, a smart AI should easily solve this problem.
It seems plausible that AGI theory has failed to produce practical algorithms so far is that because it use definitions of algorithmic complexity which are too coarse and classify as easy problems which are in fact very hard. That’s why I think that a better understanding of complexity is probably relevant for AGI research, but given the current state of knowledge, I don’t see complexity issues as fundamentally dooming the field.
Before the hard step, an early version E1 of E co-evolves with a module h which performs a similar function to H but does it much worse (imagine a rough heuristic which works for many of the cases in a relatively narrow domain). During the hard step, H appears “out of the blue” due to sheer anthropic luck after which the E1-h “wire” is replaced by an E1-H wire. After the hard step, natural selection proceeds to transform E1 into its final version E2. This picture seems to be consistent with hard step happening to our chimp-like ancestor after which natural selection rapidly transformed the result into homo sapiens sapiens.
So your claim is that going from, say, worm to chimp is relatively easy while going from chimp to human is hard and can be only accomplished by anthropic brute forcing.
This should imply that replicating the level of intelligence of a chimp should be relatively easy, while replicating what sets apart humans from chimps should be hard. This is inconsistent with current achievements in narrow-AI/operations research: Playing chess, playing Jeopardy, betting on the stock market, placing and routing a network of components in an electric grid, or a network of computers, or an integrated circuit, scheduling logistics for a large company or government agency, etc., are all things that chimps can’t do at all, human without computers can do with some difficulty, and narrow-AIs can do better than humans. On the other hand, visual object recognition in an unstructured environment like a jungle, precise 3D dynamic motion control using limbs, general planning in an unstructured environment full of uncertainty, non-eusocial coordination with other competitive agents enabling the formation of effective groups with cheater detection and punishment mechanics and non-trivial politics, are all things that wolves can do, chimps can do, humans can do but narrow-AIs can’t do yet. This suggests that worm-to-chimp cognitive abilities are harder, or at least it is harder to find effective algorithms for them, than chimp-to-human cognitive abilities.
EDIT:
If I have to guess, I would say that what sets humans apart from chimps is that humans became able to perform general-purpose computing: our brains are equipped with a sort of “universal Turing machine”, except that it is not only very slow but it has also a very short tape and it is very noisy. Yet, it works well enough that, in combination with all the other heuristic and domain-specific modules in our brain, it allows us to perform complex cognitive tasks that other animals can’t do. The fact that (AFAIK) all human languages are able to express abstract thoughts and in particular meta statements about thinking and language itself, is evidence of this fact, and it is probably also the machinery on which this general-purpose computation is implemented in our brains.
The problem with AGI is that researchers are trying to build a human-like intelligence exactly backwards compared with how evolution did: digital electronics allows us to build excellent general-purpose computers, much better than the one embedded in the human brain, but they lack all the domain-specific heuristic modules that humans acquired over million years of evolution. That’s why, IMO, narrow-AI succeeds at hard, human-only cognitive tasks and fails at the kind of things that a dog does instinctively.
Many proposed AI algorithms solve problems which are NP-hard (or worse, PSPACE-hard) in the general case. Keep in mind however, that NP-hardness and related notions are part of worst-case complexity theory, while average-complexity w.r.t. some appropriate class of “natural” problem distributions is relevant for AI and AGI
There is a beautiful NP-completeness theory for average case complexity. See Goldreich section 10.2.
No. You can prove all provable theorems by just enumerating and checking all candidate proofs.
By “algorithm” I mean a program / Turing machine that halts on all inputs.
It can be true that “magic wand” algorithms can’t exist because of complexity issues, but this would not be an issue for a humal-level AGI since humans aren’t “magic wands”.
The “magic wandness” here is quantitative rather than binary. I’m not claiming there is a discrete class of agents designated as “intelligent” producing which is hard. I’m claiming there is a quantitative measure of intelligence and the complexity of producing an agent of given intelligence grows very fast.
Consider the bit sequence generated by a strong stream chiper with an (uniformly sampled) key. It has a very small Levin complexity, but, as per the one-way function conjecture we don’t expect any AI to be ever able to efficiently predict it, as it would amount to breaking the chiper.
And yet, according to intelligence metrics based on Kolmogorov or Levin complexity, a smart AI should easily solve this problem.
This is not the case since intelligence is relative. There are problem so difficult no agent can solve them. It doesn’t mean including them in the problem distribution is an error. Unsolvable problems are problems no agent is going to solve so they don’t affect the relative intelligence of agents anyway.
...That’s why, IMO, narrow-AI succeeds at hard, human-only cognitive tasks and fails at the kind of things that a dog does instinctively.
I don’t agree that narrow AI succeeds as “hard cognitive tasks”. I think narrow AI succeeds at tasks that are very narrow and fails at tasks that require creativity (diverse solutions) like proving mathematical theorems or formulating theories of physics.
There is a beautiful NP-completeness theory for average case complexity. See Goldreich section 10.2.
Sure, there is a theory, but AFAIK it is not as developed as the theory for worst-case complexity.
I’m claiming there is a quantitative measure of intelligence and the complexity of producing an agent of given intelligence grows very fast.
Possibly true in general, but it is not obvious to me that the difference in complexity between a chimp and a human is large enough that it can be only overcome by anthropic brute-forcing.
This is not the case since intelligence is relative. There are problem so difficult no agent can solve them. It doesn’t mean including them in the problem distribution is an error. Unsolvable problems are problems no agent is going to solve so they don’t affect the relative intelligence of agents anyway.
The point is that if you try to build an agent based on a theory of general intelligence whose problem space includes (with significant probability mass) intractable problems, then any agent which has quality-of-solution performance guarantees on that problem space will have impractical resource bounds.
One way of dealing with this is to assume that our theory of general intelligence is true a priori, and thus declare the construction of a practical general intelligent agent forever impossible, barring some freak random accident that just happens to embed in it many bits of “oracle” information relevant to problem-solving in our world. Another way is to consider that our theory of general intelligence may not be well developed, after all, and therefore theoretically principled practical agents could be possible if we based them on a more refined theory that managed to remove or penalize intractable problems from its problem space.
I don’t agree that narrow AI succeeds as “hard cognitive tasks”. I think narrow AI succeeds at tasks that are very narrow and fails at tasks that require creativity (diverse solutions) like proving mathematical theorems or formulating theories of physics.
Narrow AI does not succeed at all hard cognitive tasks, but it in general it does better at them than it does at chimp-like tasks. I would say that proving mathematical theorems is a relatively narrow task once you write the theorem statement, axioms and inference rules in a precise formal way. Automatic theorem provers exist, but humans still have an edge over them for now. Formulating theories of physics requires unstructured interaction with the world, or at the very least unstructured observation. If we can’t make an AI reliably distinguish cat pictures from dog pictures, then it’s not surprising that there is no AI physicist.
In general I think that what you call “creativity” is some not sort of “magic wand” or “oracle” that came from the sky, bestowed unto us by the god of infinite random trials, rather it is the combined effect of all the heuristic modules in our brain, whose mechanics we can’t well access by introspection and verbalize.
For instance, mathematicians often say that when they reason about a theorem they “view” the mathematical structures with their mind eye. This suggests that they are co-opting their spatial reasoning abilities, evolved for things like leaping from a branch to the next, as heuristics for solving a formal logic problem. And in fact there is empirical evidence that spatial reasoning ability and mathematical reasoning ability are positively correlated. Possibly the reason why automatic theorem provers still perform worse than humans is that they lack these kind of heuristics.
The point is that if you try to build an agent based on a theory of general intelligence whose problem space includes (with significant probability mass) intractable problems, then any agent which has quality-of-solution performance guarantees on that problem space will have impractical resource bounds.
I analyze the problem in terms of continuous intelligence metrics, not in terms of binary guarantees. Agents with worse performance rate lower but it doesn’t mean you have any guarantees in the picture. As a simplified analogy, think of an exam with a collection of problems and a time-limit for solving each. The overall score is a weighted sum over the scores of individual problems. What happens if we have intractable problems in the set (problems which cannot be solved in the given time limit)? Obviously, no examinee will get non-zero score for those. However this doesn’t in any way impair the relative comparison of examinees based on the other problems.
In general I think that what you call “creativity” is some not sort of “magic wand” or “oracle” that came from the sky, bestowed unto us by the god of infinite random trials, rather it is the combined effect of all the heuristic modules in our brain, whose mechanics we can’t well access by introspection and verbalize.
I think you have a false dichotomy in there :) My claim is that these heuristic modules are so heuristic that there is no practical way to invent them without copying the answer from the actual brain.
In general, my confidence that there is a hard step is significantly higher than my confidence than it is between chimp and human.
I generally agree that computational complexity is probably relevant to the problem of AGI, but I can see several problems in your arguments:
Many proposed AI algorithms solve problems which are NP-hard (or worse, PSPACE-hard) in the general case. Keep in mind however, that NP-hardness and related notions are part of worst-case complexity theory, while average-complexity w.r.t. some appropriate class of “natural” problem distributions is relevant for AI and AGI. The relationship between worst-case complexity and average-complexity is poorly understood in the general case, and what would constitute a “natural” problem distribution is even less understood.
No. You can prove all provable theorems by just enumerating and checking all candidate proofs. Gödel’s incompleteness theorem states that there are certain statements which are “true” (in a suitable technical sense which intuitively boils down to the fact that you will never be able to find a counterexample) but are unprovable, unless arithmetic in inconsistent.
It can be true that “magic wand” algorithms can’t exist because of complexity issues, but this would not be an issue for a humal-level AGI since humans aren’t “magic wands”. A strongly super-human AGI would be much more like a “magic wand” and I would agree that the theoretical and practical possibility of this kind of intelligence is much more speculative.
I think that Solomonoff induction and the intelligence metrics based on it, even with the inclusion of resource penalties a la Levin complexity, are too strong and don’t accurately capture the notion of effectively physically realizable intelligence.
Consider the bit sequence generated by a strong stream chiper with an (uniformly sampled) key. It has a very small Levin complexity, but, as per the one-way function conjecture we don’t expect any AI to be ever able to efficiently predict it, as it would amount to breaking the chiper.
And yet, according to intelligence metrics based on Kolmogorov or Levin complexity, a smart AI should easily solve this problem.
It seems plausible that AGI theory has failed to produce practical algorithms so far is that because it use definitions of algorithmic complexity which are too coarse and classify as easy problems which are in fact very hard. That’s why I think that a better understanding of complexity is probably relevant for AGI research, but given the current state of knowledge, I don’t see complexity issues as fundamentally dooming the field.
So your claim is that going from, say, worm to chimp is relatively easy while going from chimp to human is hard and can be only accomplished by anthropic brute forcing.
This should imply that replicating the level of intelligence of a chimp should be relatively easy, while replicating what sets apart humans from chimps should be hard. This is inconsistent with current achievements in narrow-AI/operations research:
Playing chess, playing Jeopardy, betting on the stock market, placing and routing a network of components in an electric grid, or a network of computers, or an integrated circuit, scheduling logistics for a large company or government agency, etc., are all things that chimps can’t do at all, human without computers can do with some difficulty, and narrow-AIs can do better than humans.
On the other hand, visual object recognition in an unstructured environment like a jungle, precise 3D dynamic motion control using limbs, general planning in an unstructured environment full of uncertainty, non-eusocial coordination with other competitive agents enabling the formation of effective groups with cheater detection and punishment mechanics and non-trivial politics, are all things that wolves can do, chimps can do, humans can do but narrow-AIs can’t do yet.
This suggests that worm-to-chimp cognitive abilities are harder, or at least it is harder to find effective algorithms for them, than chimp-to-human cognitive abilities.
EDIT:
If I have to guess, I would say that what sets humans apart from chimps is that humans became able to perform general-purpose computing: our brains are equipped with a sort of “universal Turing machine”, except that it is not only very slow but it has also a very short tape and it is very noisy. Yet, it works well enough that, in combination with all the other heuristic and domain-specific modules in our brain, it allows us to perform complex cognitive tasks that other animals can’t do.
The fact that (AFAIK) all human languages are able to express abstract thoughts and in particular meta statements about thinking and language itself, is evidence of this fact, and it is probably also the machinery on which this general-purpose computation is implemented in our brains.
The problem with AGI is that researchers are trying to build a human-like intelligence exactly backwards compared with how evolution did: digital electronics allows us to build excellent general-purpose computers, much better than the one embedded in the human brain, but they lack all the domain-specific heuristic modules that humans acquired over million years of evolution. That’s why, IMO, narrow-AI succeeds at hard, human-only cognitive tasks and fails at the kind of things that a dog does instinctively.
There is a beautiful NP-completeness theory for average case complexity. See Goldreich section 10.2.
By “algorithm” I mean a program / Turing machine that halts on all inputs.
The “magic wandness” here is quantitative rather than binary. I’m not claiming there is a discrete class of agents designated as “intelligent” producing which is hard. I’m claiming there is a quantitative measure of intelligence and the complexity of producing an agent of given intelligence grows very fast.
This is not the case since intelligence is relative. There are problem so difficult no agent can solve them. It doesn’t mean including them in the problem distribution is an error. Unsolvable problems are problems no agent is going to solve so they don’t affect the relative intelligence of agents anyway.
I don’t agree that narrow AI succeeds as “hard cognitive tasks”. I think narrow AI succeeds at tasks that are very narrow and fails at tasks that require creativity (diverse solutions) like proving mathematical theorems or formulating theories of physics.
The “magic wand” you’re talking about is called the procrastination paradox in tiling agents.
Sure, there is a theory, but AFAIK it is not as developed as the theory for worst-case complexity.
Possibly true in general, but it is not obvious to me that the difference in complexity between a chimp and a human is large enough that it can be only overcome by anthropic brute-forcing.
The point is that if you try to build an agent based on a theory of general intelligence whose problem space includes (with significant probability mass) intractable problems, then any agent which has quality-of-solution performance guarantees on that problem space will have impractical resource bounds.
One way of dealing with this is to assume that our theory of general intelligence is true a priori, and thus declare the construction of a practical general intelligent agent forever impossible, barring some freak random accident that just happens to embed in it many bits of “oracle” information relevant to problem-solving in our world.
Another way is to consider that our theory of general intelligence may not be well developed, after all, and therefore theoretically principled practical agents could be possible if we based them on a more refined theory that managed to remove or penalize intractable problems from its problem space.
Narrow AI does not succeed at all hard cognitive tasks, but it in general it does better at them than it does at chimp-like tasks.
I would say that proving mathematical theorems is a relatively narrow task once you write the theorem statement, axioms and inference rules in a precise formal way. Automatic theorem provers exist, but humans still have an edge over them for now.
Formulating theories of physics requires unstructured interaction with the world, or at the very least unstructured observation. If we can’t make an AI reliably distinguish cat pictures from dog pictures, then it’s not surprising that there is no AI physicist.
In general I think that what you call “creativity” is some not sort of “magic wand” or “oracle” that came from the sky, bestowed unto us by the god of infinite random trials, rather it is the combined effect of all the heuristic modules in our brain, whose mechanics we can’t well access by introspection and verbalize.
For instance, mathematicians often say that when they reason about a theorem they “view” the mathematical structures with their mind eye. This suggests that they are co-opting their spatial reasoning abilities, evolved for things like leaping from a branch to the next, as heuristics for solving a formal logic problem. And in fact there is empirical evidence that spatial reasoning ability and mathematical reasoning ability are positively correlated. Possibly the reason why automatic theorem provers still perform worse than humans is that they lack these kind of heuristics.
I analyze the problem in terms of continuous intelligence metrics, not in terms of binary guarantees. Agents with worse performance rate lower but it doesn’t mean you have any guarantees in the picture. As a simplified analogy, think of an exam with a collection of problems and a time-limit for solving each. The overall score is a weighted sum over the scores of individual problems. What happens if we have intractable problems in the set (problems which cannot be solved in the given time limit)? Obviously, no examinee will get non-zero score for those. However this doesn’t in any way impair the relative comparison of examinees based on the other problems.
I think you have a false dichotomy in there :) My claim is that these heuristic modules are so heuristic that there is no practical way to invent them without copying the answer from the actual brain.
In general, my confidence that there is a hard step is significantly higher than my confidence than it is between chimp and human.