Measuring based on bits doesn’t seem to capture what we care about.
Consider the following two functions: F(x,y) = x+y and G(x,y) = the value of boolean expression x with the variables given truth-assignment y.
In each case, I am given some value x and z and want to pick a y so that F(x,y) =z or G(x,y) = z.
Doing this for F is trivial, and for G is not known to be tractable. An AI able to efficiently solve SAT is much more powerful than being able to do subtraction. But you can arrange to have the same chance of succeeding by random chance in each case.
A definition that says that gnu “bc” is as powerful as an oracle for all problems in NP is not a very useful definition.
Moral: Knowing the chance to succeed “by chance” doesn’t tell you much about how sophisticated an algorithm is.
Measuring based on bits doesn’t seem to capture what we care about.
Consider the following two functions: F(x,y) = x+y and G(x,y) = the value of boolean expression x with the variables given truth-assignment y. In each case, I am given some value x and z and want to pick a y so that F(x,y) =z or G(x,y) = z.
Doing this for F is trivial, and for G is not known to be tractable. An AI able to efficiently solve SAT is much more powerful than being able to do subtraction. But you can arrange to have the same chance of succeeding by random chance in each case.
A definition that says that gnu “bc” is as powerful as an oracle for all problems in NP is not a very useful definition.
Moral: Knowing the chance to succeed “by chance” doesn’t tell you much about how sophisticated an algorithm is.