8 ms·
> 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?
by 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...