= 27d567bc2d48d9f40e9ccc20ea370b15)
Psy-Kosh comments on Rationality Quotes 1 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (28)
Eliezer: Am a bit confused on what you mean. Do you claim that there cannot be randomized algorithms that can solve problems in less expected computing time than any deterministic algorithm would take for that problem?
As I understand it (and computational complexity people please please please correct me if I'm way off on this) there's significant theoretical reason to suspect that probabalistic algorithms are strictly more powerful. That is, can be expected to solve some problems faster than the best possible deterministic algorithms.
Proof that this is not the case:
For any probabilistic algorithm A and problem P, there exists some sequence of random actions, among the many of which A is capable, that solves the problem the problem the fastest. (It doesn't take the same amount of time each time, so there has to be some shortest possible time it can take.) Then, there is a deterministic algorithm A' that always takes that series of actions on that problem.
But... I mean, when you combine the running time with the effort it takes to find the better, deterministic solution, it might not be worth it. It’s only worth it if you can generalize the solution to other problems. So I guess randomized algorithms are better when the time you spend thinking about how to do it better pays for itself in time saved, summed across all the problems you apply that thinking to.
EDIT: Oops that last sentence is basically the opposite of what I was trying to say