Oscar_Cunningham comments on Can noise have power? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (42)
I suppose that there are really 6 different complexities. Let x be the random numbers you pick and let y be the input you get. Let f(x,y) be the time your algorithm takes on that instance. We can maximise or take the expected value for each of x and y, in either order.
There's not one best way to put a distribution on the possible inputs, so computer scientists who don't want to do this can only look at 2, 3, and 6. Then problems that can be solved in poly time according to 2 are the ones in BPP, and those that can be solved in poly time according to 6 are the ones in P (you don't use your RNG if it's trying to kill you). I don't know if the corresponding class for 3 has a name, but it doesn't seem very interesting.
EDIT: You also don't want to use your RNG if you're being judged by 4 or 5, so these both correspond to the complexity class where you judge by average time and you don't have a RNG. Then 1 corresponds to the complexity class where you're judged by average time and you do have an RNG. These complexity classes are known to be the same, since as Scott says