I don’t understand why this was linked as a response at all. Randomization is conjectured not to help in the sense that people think P = BPP. But there are cases where randomization does strictly help (wikipedia has a partial list: http://en.wikipedia.org/wiki/Randomized_algorithm).
My point was about sociology. Complexity theorists are not bashing each other’s heads in over whether worst case or average case analysis is “better,” they are proving theorems relating the approaches, with the understanding that in some algorithm analysis applications, it makes sense to take the “adversary view,” for example in real time systems that need strict guarantees. In other applications, typical running time is a more useful quantity. Nobody calls worst case analysis an apostate technique. Maybe that’s a good example to follow. Keep religion out of math, please.
I agree with this. That was supposed to be the point of the post.
Randomization is conjectured not to help in the sense that people think P = BPP.
Even if P = BPP, randomization still probably helps; P = BPP just means that randomization doesn’t help so much that it separates polynomial from non-polynomial.
Er, yes?
I don’t understand why this was linked as a response at all. Randomization is conjectured not to help in the sense that people think P = BPP. But there are cases where randomization does strictly help (wikipedia has a partial list: http://en.wikipedia.org/wiki/Randomized_algorithm).
My point was about sociology. Complexity theorists are not bashing each other’s heads in over whether worst case or average case analysis is “better,” they are proving theorems relating the approaches, with the understanding that in some algorithm analysis applications, it makes sense to take the “adversary view,” for example in real time systems that need strict guarantees. In other applications, typical running time is a more useful quantity. Nobody calls worst case analysis an apostate technique. Maybe that’s a good example to follow. Keep religion out of math, please.
I agree with this. That was supposed to be the point of the post.
Even if P = BPP, randomization still probably helps; P = BPP just means that randomization doesn’t help so much that it separates polynomial from non-polynomial.