The Unique Games Conjecture and FAI: A Troubling Obstacle

I don't think the difficulties in adapting our moral intuitions into a self-consistent formal system (e.g. the Repugnant Conclusion) is a problem of insufficient optimisation power per se, its more the case that there are multiple systems within the brain (morality, intuitions, logic) and these are not operating in perfect harmony. This doesn't mean that each individual system is not working ok in its own way.

Surely designing an engine, or writing a novel, or (... you get the gist) are complex optimising problems with many constraints, and yet it seems that humans can at least approximately solve these problems far faster than brute-force trial and error.

AFAICT the UGC was saying that there exist insoluble problems, not that these problems are actually common. It seems to me like Godel's incompleteness theorem - there are statements which are true but which cannot be proved, but this doesn't mean that no statement can be proved, or that mathematics is pointless. At the end of the day regardless of whether or not the fundamental underpinning of mathematics are on shaky ground, or whether there are unprovble theorems and unsolvable problems, the actual mathematics that allows us to build aeroplanes works, and the planes fly.

We are used to imagining spectacular failures resulting from tiny mistakes, on LW. An AI that's designed to make people smiles creates a monstrous stitching of fleshy carpet. But we are not used to imagining failures that are less obvious, but still awful. I think that's a problem.

I think people understand that this is a danger, but by nature, one can't spend a lot of time imagining these situations. Also, UGC has little to do with this problem.

Every single physical theory that is currently considered fundamental is local, from general relativity to quantum mechanics.

I dislike the wikipedia article on the subject, it gives far to much credence to the fringe notion that maybe there is a way to exploit entanglement to get faster-than-light information transfer.

The quantum nonlocality article is much better, it correctly points out that

it (quantum nonlocality) does not allow for faster-than-light communication, and hence is compatible with special relativity.

It follows from special relativity.

This is interesting, can you expand on this? I feel there clearly are some arguments in complexity theory against AI as an existential risk, and that these arguments would deserve more attention.

Sure.

There's a basic argument that if P != NP then we should expect recursive self-improvement to be hard because many of the problems that would be involved in self-improvement (e.g. memory management, circuit design, protein folding) are NP-hard or NP-complete.

This argument in this form suffers from two problems:

First, it isn't clear what the constants in question are. There could be an exponential time algorithm for solving your favorite NP-complete problem but the algorithm is so efficient on instances of any size that matters that it doesn't end up impacting things. It isn't completely clear how serious this problem is. On the one hand, as of right now, it looks like "polynomial time algorithm if and only if has practical algorithm" is a decent heuristic even though it has exceptions. On the other hand, we've seen even in the last few years important examples where careful improvements to algorithms can drastically improve practical running speed. One major example is linear programming.

Second, most of the NP-complete problems we want to solve in practice are optimization problems. So one might hope that even if a problem is NP-hard, getting close to an optimal solution will still be doable efficiently. Maybe for most of these problems, we can expect that as the problem instances get large we actually get really efficient approximations for things which are very close to the best possible solutions.

UGC addresses both these points- the first point in a weak way, and the second point in a strong way. Prior to the Unique Games Conjecture, there was a major theorem called the PCP theorem. This is one of the few unambiguously deep results in computational complexity and it has important results that say that in many cases approximation is tough. If UGC is true, then the idea that approximation is tough becomes even more true. Consider for example the problem of minimal vertex cover(which shows up in a bunch of practical contexts and is NP-complete). Now, there is an algorithm which will approximate minimal vertex cover within a factor of 2 or so, and the algorithm is simple, and it isn't a bad idea try to work it out. PCP implies that no algorithm can in polynomial time do better than about 1.3 times the best possible, but there's a gap between 2 and 1.3. It turns out that UGC implies that a factor of 2 is really the best unless P=NP (more formally that approximating minimal vertex cover within a factor of 2 would be NP complete). This is discussed in some detail (with spoilers for the above recommended exercise) here. This is one of many problems where UGC implies that some fairly straightforward algorithm really is best possible unless P=NP. More precisely, if UGC is true, then in a wide variety of circumstances beating approximations one get from semidefinite programming is not doable.

So, if one believes UGC, then optimization is tough. This addresses primarily issue 2. How does this address issue 1? Well, as a rough heuristic, if all these approximation problems are NP-complete even for very weak approximations, and P != NP, then one should expect that even improving one's demand for the closeness of approximation a tiny amount will cause the constants (if not even also the asymptotics) to shoot up.

This isn't the entire story: For example, it ignores any context that quantum computing may impact things. Right now, the general consensus is that it is very unlikely that a quantum computer will be able to solve NP-complete problems in polynomial time. Formally, we believe that NP is not contained in BQP. But since BQP contains P, this is a much stronger claim than P != NP. On the other hand, if one believes UGC, then one also gets that if one does believe that NP is not contained in BQP then one should also believe that many approximate optimization problems cannot be done substantially better on a quantum computer than they can on a classical computer. Some people have also raised the possibility that quantum computers may somehow even if they don't improve the asymptotics for some problems may improve the constants: there's no intrinsic, theoretical, or strong empirical reason to believe this (with the exception of Grover's algorithm), but it seems like enough of a concern that I consider the idea of letting any nascent AI have access to a functioning quantum computer to be a Really Bad Idea (TM).

It is also worth noting that even if P=NP in some strong sense, this doesn't mean that recursive self-improvement necessarily can happen, although it does it make it more likely: physical limits and other issues may still come into play. It is worth keeping in mind that even if one has really fast optimization algorithms one cannot optimize beyond what is actually possible. To put it another way, if you have a bunch of needles in a haystack, even if you can search haystacks really fast, if none of the needles are made of gold you won't find any gold needles.

Replying separately(rather than editing), to make sure this comment gets seen.

It is worth noting that although UGC may not be true, weaker versions of UGC get many similar results. So for example, one can get most results of UGC if one believes that NP <= P^U/poly where U is a unique games oracle. Then one would get similar results under the assumption that the polynomial hierarchy does not collapse. Also if one instead of believing that UGC is NP-complete one believes that UGC has no polynomial time algorithm then you get some of the same results or very similar results.

Since many people don't assign that high a probability to UGC, it may be worth asking what evidence should cause us to update to assign a higher probability to UGC (short of a proof). There seem to be four obvious lines of evidence:

First, showing that some problems expected to be NP-intermediate (e.g. factoring, graph isomorphism, ring isomorphism) can be reduced to unique games. (Remark: the obvious candidate here would be graph isomorphism. I'm not aware of such a reduction but my knowledge of the literature here is not very good.) This would be strong evidence for at least some of the weaker versions of UGC, and thus evidence for UGC.

Second, showing that the attempted methods to solve unique games fail for intrinsic reasons that cannot be overcome by those methods. Right now, the two noteworthy methods are Sums of Squares and QAOA. If there are fundamental barriers to variants of either method working that would make UGC substantially more plausible.

Third, proving more of the inapproximation results implied by UGC by methods independent of UGC. There's been some progress on this, but it may turn out that the inapproximations implied by UGC are the correct bounds even as UGC is false. At the same time, even as these sorts of results are proved, they make UGC less directly useful for trying to actually estimate whether recursive self-improvement can substantially occur.

Fourth, it may be possible to prove not that some unexpected collapse occurs when given access to a unique games oracle that would be unlikely unless UGC is true. Obvious candidates would be something like NP < co-NP^U, or NP < P^U/poly.

What do you mean by classes? I'm pretty sure the UGC applies to all sorts of constraint satisfaction problems, not just a certain kind of them.

Some CSPs already have efficient exact or approximate algorithms. (For example, we can approximate Max-Cut to within a factor of 0.878, or test if a graph has a 2-coloring, in polynomial time.) The UGC is normally stated about a single class of CSPs, though I'm sure it has implications for some other classes as well.

I agree. But what are the odds it's best case, either? I'm not saying that we're doomed and have no chance of evaluating things. I'm saying that this is a potential difficulty I hope someone looks into further.

The impression I've always gotten was that average-case instances of many NP-complete problems are believed to be tractable. JoshuaZ points out that this may not be true, but it seems from some skimming that results along that direction are less like "a typical instance is hard" and more like "we can generate random hard instances semi-efficiently".

This is interesting from a cryptographical point of view: it would be nice to have a one-way function whose hardness depended on P vs NP rather than a weaker assumption. But if we encounter a constraint satisfaction problem in the real world, it is not going to come even from an adversarially chosen random distribution.

It is, in fact, likely that such a problem will have some additional exploitable structure that will make it easier than the typical instance (which we already don't know is hard). An example of this is metric TSP. This would be the "best case" you're referring to.

Can you elaborate on how we go from "approximating is hard" to "the average instance is hard"? (Or point me to somewhere I can read up on it?)