Complexity No Bar to AI (Or, why Computational Complexity matters less than you think for real life problems)

post by Noosphere89 (sharmake-farah) · 2022-08-07T19:55:19.939Z · LW · GW · 14 comments

This is a link post for https://www.gwern.net/Complexity-vs-AI

Contents

14 comments

Basically an article about why knowing a problem is in a certain complexity class does not mean AGI can't do that problem. It's some evidence, but usually isn't enough unless 2-3 or more assumptions are right..

The biggest reasons are these:

2. Giving up determinism and using randomized algorithms which are faster but may not return an answer or a correct answer (they typically can be run many times if correctness is important; after a few times, the probability of an error will be smaller than the probability that the computer hardware has suffered a glitch due to cosmic rays); randomization can be applied to algorithms and to ⁠data structures⁠.

5. Giving up optimality and computing an approximation of the optimal answer (often very close to the optimal answer) Already mentioned is 3-SAT/TSP, for which there is a ⁠World Tour of 1,904,711-cities which has been solved with a tour within 0.0474% of the optimal tour by 2007, and planning problems soluble by translation into SAT form can have millions of clauses & variables, enabling such silly applications as ⁠drawing portraits & art or unscrambling images using the TSP; Naam gives chemistry as an example by noting that while the exact physics is totally intractable, approximations which are much more feasible are used. The last fraction of a percentage point of optimality can take truly enormous amounts of computation to squeeze out.

Basically, we can tolerate not getting the algorithm to work every time, since we can just run it again and we can reduce error rates to levels far below the cosmic ray error rate. Also, the perfect is not the enemy of the good, so we can accept a 99.999% approximation, and that's enough to design new technologies.

Lastly, constant factors are an issue:

Are all implementations equally fast?

“For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.” "Alan Perlis

Premise 3 ignores that complexity classes by design try to abstract away from the ‘constant factors’ which is the computation time determined not by input size but by the details of computer architectures, implementations, and available computing hardware. AIs and humans can be equally bound by asymptotic complexity, but still differ on performance.

But with carefully optimized code, proper use of the cache hierarchy⁠, and specialized hardware (eg. GPUs, ASICs), it is possible to see ⁠performance gains of multiple orders of magnitude⁠, which implies that one can increase the input size several times before hitting the scaling way that another agent might who paid less attention to constant factors. (Computational chemistry may be intractable, even with approximations, on classical hardware—but what about if one has a quantum computer with a few hundred qubits, enough that one can do quantum simulation?) The importance of constant factors is one of the major traps in practical use of complexity classes: a fancy algorithm with a superior complexity class may easily be defeated by a simpler algorithm with worse complexity but faster implementation.⁠⁠6 (One reason that programmers are exhorted to benchmark, benchmark, benchmark!) This doesn’t disprove the complexity class, which is about asymptotic scaling and will still kick in at some point, but if it’s possible to double or dectuple or more the input, this is enough of an increase that it’s hard to dismiss the difference between best and worst agents’ problem sizes as being only ‘slight’ Finally, increased resource use / brute force is always an option for a powerful agent. Particularly in his second post, Naam’s argument assumes fixed resources. This might be relevant to a few scenarios like an AI permanently confined to a single computer and unable to access more resources—but then, how intelligent could such an AI possibly be if it can’t get out? However, thanks to its intelligence, humanity now controls a large fraction of the biosphere’s energy and with a supercomputer, or tech giants like Google or Amazon who control millions of processor-cores, can compute things totally out of reach of other agents; no limits to the amount of computation that can be done on (or off) Earth have yet been reached. Increases in computing resources of thousands or millions of times, along with larger timescales, can overcome the asymptotic to achieve the next intelligence increase; if a human-level AI can ‘only’ accomplish a few dozen doublings, well…

You should really read Gwern's full post, it has a lot of insights.

One final note on complexity: Protein Folding was predicted to never progress that much because it was NP-Hard for computers. Suffice it to say with AlphaFold 2 and Deepmind releasing 200 million proteins, the prediction is very wrong now.

EDIT: I no longer endorse the strong version of no evidence from complexity theory of my argument above, so I am removing parts of my post and defending a weaker claim than I originally did.

14 comments

Comments sorted by top scores.