[thedatamonger]

From the related article: 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]

I 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]

> 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]

Can’t you build search from decision by deciding on every possible input?