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.
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.