The problem with this definition is that it focusses too much on the details of the computational substrate. Suppose the programming language used has a built in function for matrix multiplication, and it is 2x as fast as any program that could be written within the language. Then any program that does its own matrix multiplication will be less intelligent than one that uses the built in functions.
“A with X resources beats program B with X resources, for any B” could be true if A is just B with the first few steps precomputed. It focusses too much on the little hackish tricks specific to the substrate.
Maybe say that two algorithms A, B are equivalent up to polynomial factors if there exists a polynomial p(x) so that A with p(x) compute beats B with X compute for all x, and likewise B with p(x) compute beats A with x compute.
Yes, your restatement feels to me like a clear improvement.
In fact, considering it, I think that if algorithm A is “truly more intelligent” than algorithm B, I’d expect if f(x) is the compute that it takes for B to perform as well or better than A, f(x) could even be super-exponential in x. Exponential would be the lower bound; what you’d get from a mere incremental improvement in pruning. From this perspective, anything polynomial would be “just implementation”, not “real intelligence”.
The problem with this definition is that it focusses too much on the details of the computational substrate. Suppose the programming language used has a built in function for matrix multiplication, and it is 2x as fast as any program that could be written within the language. Then any program that does its own matrix multiplication will be less intelligent than one that uses the built in functions.
“A with X resources beats program B with X resources, for any B” could be true if A is just B with the first few steps precomputed. It focusses too much on the little hackish tricks specific to the substrate.
Maybe say that two algorithms A, B are equivalent up to polynomial factors if there exists a polynomial p(x) so that A with p(x) compute beats B with X compute for all x, and likewise B with p(x) compute beats A with x compute.
Yes, your restatement feels to me like a clear improvement.
In fact, considering it, I think that if algorithm A is “truly more intelligent” than algorithm B, I’d expect if f(x) is the compute that it takes for B to perform as well or better than A, f(x) could even be super-exponential in x. Exponential would be the lower bound; what you’d get from a mere incremental improvement in pruning. From this perspective, anything polynomial would be “just implementation”, not “real intelligence”.