4 ms·
From the related article: https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-
by thedatamonger 2y ago
From the related article:
https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/ https://www.quantamagazine.org/avi-wigderson-complexity-theo...
> ... if a statement can be proved, it also has a zero-knowledge proof.
Mind blown.
>Feeding the pseudorandom bits (instead of the random ones) into a probabilistic algorithm will result in an efficient deterministic one for the same problem.
This is nuts. AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude.
If I'm living in noobspace someone please pull me out.
- IshKebab 2y agoI don't know exactly what it's saying but it definitely isn't that. AI already uses pseudorandom numbers and is deterministic. (Except some weird AI accelerator chips that use analogue computation to improve efficiency.)
- ilya_m 2y ago> AI is a probabilistic computation ... so what they're saying - if i'm reading this right - is that we can reduce the complexity of our current models by orders of magnitude. Unfortunately, no. First, the result applies to decision, not search problems. Second, the resulting deterministic algorithm is much less efficient than the randomized algorithm, albeit it still belongs to the same complexity class (under some mild assumptions).
- mxkopy 2y agoCan’t you build search from decision by deciding on every possible input?