because any solver specialized to the evolutionary subset is guaranteed to fail once the promise is removed; outside that tightly curated domain, the mapping reverts to an unbounded and intractable instance class.
There are plenty of expansions you could make to the “evolutionary subset” (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable.
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the “standard abstraction schemes” do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
In many hardness and impossibility results, “adversarial / worst-case” are doing nearly all of the work in the proof, but if you’re just trying to build some nanobots you don’t care about that. Or more prosaically, if you want to steal some cryptocurrency, in real life you use a side-channel or 0-day in the implementation (or a wrench attack); you don’t bother trying to factor large numbers.
IMO it is correct to mostly ignore these kinds of things when building your intuition about what a superintelligence is likely or not likely to be able to do, once you understand what the theorems actually say. NP-hardness says, precisely, that “if a problem is NP-hard (and P≠NP), that implies that there is no deterministic algorithm anyone (even a superintelligence) can run, which accepts arbitrary instances of the problem and finds a solution in time steps polynomial in the size of the problem instance.”. This statement is precise and formal, but unfortunately it doesn’t mention protein folding, and even the implications that it has for an idealized formal model of protein folding are of limited use when trying to predict what specific proteins AlphaFold-N will / won’t be able to predict correctly.
Let’s look at the most interesting of your arguments first:
“There are plenty of expansions you could make to the “evolutionary subset” (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable.”
This response treats the argument as if it were an appeal to worst-case complexity theory—i.e., “protein folding is NP-hard, therefore superintelligence can’t solve it outside the evolutionary subset.” My point rests on entropy and domain restriction, not on NP-hardness per se. It was just convinient to frame it in these terms. And so the existence of trivial or nontrivial supersets where hardness theorems don’t apply is irrelevant. But even so: What goes in a computer is already framed in an abstraction sufficient to determine NP-ness.
In an weird way way, you are actually agreeing with what was written.
My argument is not: “the moment we enlarge the domain, NP-hardness dooms us.” My argument is: “the moment we enlarge the domain, the entropy of the instance class can increase without bound, and the learned model’s non-uniform ‘advice string’ (its parameters) no longer encodes the necessary constraints.”
One point is demonstrably meh:
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the “standard abstraction schemes” do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
Cmputational hardness does retain some relevance for AI, since AI systems exhibit the same broad pattern of struggling with problems whose structure reflects NP-type combinatorial explosion. Verifying a candidate solution can be easy, while discovering can be difficult, impressing your crush “NP-like”: it is straightforward to determine whether a remark is effective, but difficult to determine in advance what remark will succeed, with or without AI.
Now again, I am not discussing complexity, this is more like a predicate argument for why something is a non sequitur.
There are plenty of expansions you could make to the “evolutionary subset” (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable.
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the “standard abstraction schemes” do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
In many hardness and impossibility results, “adversarial / worst-case” are doing nearly all of the work in the proof, but if you’re just trying to build some nanobots you don’t care about that. Or more prosaically, if you want to steal some cryptocurrency, in real life you use a side-channel or 0-day in the implementation (or a wrench attack); you don’t bother trying to factor large numbers.
IMO it is correct to mostly ignore these kinds of things when building your intuition about what a superintelligence is likely or not likely to be able to do, once you understand what the theorems actually say. NP-hardness says, precisely, that “if a problem is NP-hard (and P≠NP), that implies that there is no deterministic algorithm anyone (even a superintelligence) can run, which accepts arbitrary instances of the problem and finds a solution in time steps polynomial in the size of the problem instance.”. This statement is precise and formal, but unfortunately it doesn’t mention protein folding, and even the implications that it has for an idealized formal model of protein folding are of limited use when trying to predict what specific proteins AlphaFold-N will / won’t be able to predict correctly.
Let’s look at the most interesting of your arguments first:
“There are plenty of expansions you could make to the “evolutionary subset” (some of them trivial, some of them probably interesting) for which no theorem from complexity theory guarantees that the problem of predicting how any particular instance in the superset folds is intractable.”
This response treats the argument as if it were an appeal to worst-case complexity theory—i.e., “protein folding is NP-hard, therefore superintelligence can’t solve it outside the evolutionary subset.” My point rests on entropy and domain restriction, not on NP-hardness per se. It was just convinient to frame it in these terms. And so the existence of trivial or nontrivial supersets where hardness theorems don’t apply is irrelevant. But even so: What goes in a computer is already framed in an abstraction sufficient to determine NP-ness.
In an weird way way, you are actually agreeing with what was written.
My argument is not: “the moment we enlarge the domain, NP-hardness dooms us.”
My argument is: “the moment we enlarge the domain, the entropy of the instance class can increase without bound, and the learned model’s non-uniform ‘advice string’ (its parameters) no longer encodes the necessary constraints.”
One point is demonstrably meh:
In general, hardness results from complexity theory say very little about the practical limits on problem-solving ability for AI (or humans, or evolution) in the real world, precisely because the “standard abstraction schemes” do not fully capture interesting aspects of the real-world problem domain, and because the results are mainly about classes and limiting behavior rather than any particular instance we care about.
Cmputational hardness does retain some relevance for AI, since AI systems exhibit the same broad pattern of struggling with problems whose structure reflects NP-type combinatorial explosion. Verifying a candidate solution can be easy, while discovering can be difficult, impressing your crush “NP-like”: it is straightforward to determine whether a remark is effective, but difficult to determine in advance what remark will succeed, with or without AI.
Now again, I am not discussing complexity, this is more like a predicate argument for why something is a non sequitur.