3 ms·
Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one. So its not going do the kind of game changing class breaking wor
by jvanderbot 1y ago
Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one. So its not going do the kind of game changing class breaking work you're looking for. You know, where random is the only way.
How randomization helps is by making it much easier to design algorithms. E.g. Verifying a solution is cheap, so proving your random choice is in some class of good choices and making an algorithm that turns that into a solution is still an interesting approach and opens up solutions to things we cant yet solve.
Derandomizing as presented apparently means proving for a few random but careful choices you're in the funnel towards the right solution, or (hopefully) can detect otherwise, and a few transformations or reasonably performant steps produce your solution.
- lifeinthevoid 1y ago> Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one Oh, that's cool, do you have a reference for that?
- jvanderbot 1y agoTFA (edit: in the politest way)
- danhite 1y ago>> Well in fact we know (if P! = NP) that for any randomized ALG there's a good deterministic one > Oh, that's cool, do you have a reference for that? The OP article has such a reference, but theirs is paywalled, and perhaps you missed it, so you may wish to see this no paywall link to the paper: Hardness vs. Randomness by Noam Nisan & Avi Wigderson https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HAR...
- furyofantares 1y agoI'm not looking for any kind of game changing class breaking work. I don't think I'm being understood here at all. I must have put too much emphasis on PRNG or on maybe there's a more intelligent way to sample - you can ignore those comments. I just think it's framed poorly to make it sound more counterintuitive than it is.
- jvanderbot 1y agoIt happens. Sorry for misunderstanding