3 ms·
Really interesting. I've often wondered this, but always thought that it would be too good to be true in most cases. > But in two papers published in the 1990s
by karmakaze 6y ago
Really interesting. I've often wondered this, but always thought that it would be too good to be true in most cases.
> But in two papers published in the 1990s, Wigderson and his collaborators proved that under certain assumptions, it’s always possible to convert a fast random algorithm into a fast deterministic algorithm. The result established that the complexity class known as “BPP” was exactly equal to the complexity class P. It tied decades of work on randomized algorithms neatly into the main body of complexity theory and changed the way computer scientists looked at random algorithms.
“I think that today almost anybody you asked would tell you randomness is weak rather than that randomness is powerful, because, under assumptions we strongly believe, randomness can be eliminated,” said Wigderson.
- YaSamPoSebe 6y ago"The result established that the complexity class known as “BPP” was exactly equal to the complexity class P" - oh no it did not :)