The story so far: our three characters, :), 8) and :|, have discussed in detail an approach that π has to proving complexity lower bounds. At the beginning of the discussion, they established that the idea would be very unlikely to prove lower bounds for circuit complexity, which is what would be needed to prove that PNP. More recently, they have given arguments that strongly suggest that the idea cannot prove interesting new bounds even for weaker models. In this segment of the dialogue, they nevertheless consider what kinds of methods would be needed in order to prove lower bounds for circuit complexity (as opposed to formula complexity). They don’t really get anywhere, and this part of the discussion ends rather abruptly, but they mention one or two interesting facts along the way.

***************************************

π After all that, I have to say that I’m still slightly disappointed that it seems that even if the ideas I’ve been having *could* be got to work, they are most unlikely to show that PNP.

π I didn’t really understand why not. Can somebody remind me?

8) I can. Recall that a *formal complexity measure* is a function such that for every basic function , for every , and and are both at most for every and . Now if all you know about is that it is a formal complexity measure, then all you can deduce from the fact that is that has formula size at most . Therefore, if there exist functions with low circuit complexity but very high formula size, then one cannot use a formal complexity measure to prove that PNP unless it has some further properties.

π Hmm … it seems that you need a pretty strong statement to back up what you’ve just said. If I can find a formal complexity measure and also a function in NP with , then that will prove that PNP unless there exist functions of polynomial circuit complexity and formula size at least . Is it believed that a function of polynomial circuit complexity could have exponentially large formula size, for instance?

8) I’d have to check. But if you take a fairly random circuit, then the obvious way of turning it into a formula certainly does require the size of that formula to be exponential, and it’s hard to see how to do any better.

π How do you mean, “the obvious way of turning it into a formula”?

8) Well, if you’ve got a sequence of functions with each one either a basic function or a Boolean operation of two earlier functions, you can just build up a formula in the same way. For instance, if we write for the th basic function, then we could define a function by taking , , , , , , . Unpacking this, we get

If you don’t count the basic functions in the definition of circuit complexity, then the circuit complexity of is 3, while this formula has length 4. And that lack of economy goes up rapidly as more and more functions in the circuit depend on earlier ones. If you play around with it a bit, you’ll be convinced.

π Great, thanks, I believe you. In fact, it’s sort of obvious really: as you increase the length of the sequence of functions, to get the formula complexity of you add the formula complexities of earlier functions, whereas to get the circuit complexity you just add 1. So the formula complexity really does look as though it goes up much more rapidly. Of course, that’s not a rigorous proof, since there might be some less obvious way of producing a formula that was far shorter. But I agree that that looks very unlikely.

Actually, couldn’t one use this thought to tackle the formula-size question? Perhaps one way to produce a function in NP with large formula size is actually to produce a function in P with large formula size by picking a random sequence of Boolean operations.

8) Two comments on that. One is that a random sequence of Boolean operations will give you a function of low circuit complexity, but that’s not quite the same as a function that can be computed in polynomial time. The second is that you’ll still need a proof that your random function has high formula complexity.

[*See this comment of Ryan Williams for an explanation of why the first objection can be dealt with.*]

π I was wondering whether maybe it would have *maximal* formula complexity in the following sense: the obvious formula really is the best you can do, as long as you obey some simple rules that don’t allow you to produce a shorter formula in a trivial way. For example, you can shorten to , but that depended on the fact that and have some overlap. Perhaps in the random case you just wouldn’t get that kind of overlap.

8) If that’s the sort of thing you’d like to do, then let me tell you something depressing. It’s a well-known approach that morally ought to give a lower bound for formula complexity, but nobody has managed to get it to work.

Suppose that are formulae, and that they depend on disjoint sets of variables. Suppose also that is a formula that depends on variables. Then you might expect that the shortest formula for computing the function is the obvious one, where you compute for each and then apply . Therefore, if has formula size and all the have formula size , you might expect the formula size of to be .

Now choose a random function of variables. This will have formula size , which is somewhere close to , by a simple counting argument. We can then build a new function , where it is to be understood that we are applying to disjoint sets of variables. Then has formula size , if we believe our previous argument. Then we can build another function , which now depends on variables and has formula size , and so on. We keep going until we use all variables, which happens when we reach the function , where . This function has formula size , which equals , which is about , which is superpolynomial. But clearly the function can be computed in polynomial time, since can (as it depends on just variables).

π That’s pretty cool. So what’s wrong with the argument?

8) Just the fact that I stated a major lemma and didn’t prove it. I didn’t justify the statement that the shortest formula for is the obvious one. And I think that’s an unsolved problem: certainly, it’s either an unsolved problem or someone’s found a counterexample, since I know that the formula-size problem is still open.

π I suppose another point is that even if this argument worked, it wouldn’t actually give a superpolynomial bound for formula size, because the function that you used to build everything up was chosen randomly rather than given by some algorithm.

8) You’re right. In the absence of any further tricks, what this argument would show is that there was a function of polynomial circuit complexity and superpolynomial formula size. [*See again Ryan Williams’s comment.*] But even without any new ideas, one would in principle be able to use this approach to obtain arbitrarily large polynomial lower bounds for formula size.

π How would you do that?

8) Well, even if we can’t choose a random function to get things going, we could in theory take some fixed and find a suitable function by brute force.

π Sorry to be slow, but how would you do even that?

8) You’d look at every single Boolean function of variables and every single formula of size at most, say, , and pick out a Boolean function that is not given by one of the formulae.

π Wow. There are Boolean functions in variables, so that’s going to take a pretty long time, even for very small .

8) Yes. That’s why I used the phrase “in principle” earlier. But even distinguishing between polynomial circuit complexity and polynomial formula size would be very interesting.

π Er, excuse me.

8) Yes?

π We seem to have got sidetracked. I was just wondering whether it would be possible to return to the main topic.

8) How do you mean, “the main topic”?

π I mean the question of whether any of the ideas we’ve been discussing could be used to prove that PNP rather than just the weaker statement that some explicit functions have large formula size.

8) Ah yes, your obsession with the million-dollar prize …

π That’s not fair. I absolutely agree that the formula-size problem is a great problem, but that doesn’t mean we shouldn’t even *think* about circuit complexity.

8) Relax, I’m just teasing you. *Everyone* would prefer to solve the P versus NP problem if there was a chance of doing so, including me.

π OK, well perhaps you’d like to answer a question that’s been bugging me. Here is a proof that the notion of a formal complexity measure is very natural if one is thinking about formula size. We’ve already discussed it, but let me quickly go through it again just so I can be clear about the question I want to go on to ask.

One can arrive at the notion of a formal complexity measure by asking the following question: if we define to be the formula size of , then what properties are satisfied by ? And one quickly observes that , and that and are both at most . Having done that, one can define a formal complexity measure to be any function with these properties, and one then observes that is the largest possible formal complexity measure.

8) Indeed.

π The idea behind our previous discussion was this. In principle, one can prove that a function has large formula size by finding a formal complexity measure and proving that is large. But we have two problems. Obviously, to increase our chances of success, we’d like to be as large a function as possible. But if we take itself then we have done precisely nothing: we’ve shown that a function has large formula size if and only if it has large formula size. So there’s another requirement: we want to be a function that we can actually say something about, so that proving that is large is strictly easier than proving that has large formula size. However, here we run into the problem that if is too simple, and in particular if it can be calculated using a polynomial-time algorithm (in ), then it will almost certainly not work.

8) Let me quickly interject here that in their paper Razborov and Rudich showed that if a formal complexity measure is ever large, then it will be large for a positive fraction of all Boolean functions. So if you believe that natural proofs can’t solve the formula-size problem either, as you seem to do, then you definitely can’t use a polynomially computable formal complexity measure.

π Right, that just confirms what I was saying.

Anyhow, on to my question. I’m just wondering whether we can go through the whole thought process again, but this time for circuit complexity. But I seem to have got stuck at the very first step.

8) How do you mean?

π Well, the first step of the previous argument was to look for properties satisfied by the function So I thought I’d define to be the circuit complexity of and try to find some properties of But the properties I am coming up with don’t seem to be strong enough. For instance, if you know and what can you say about ? The best I can come up with is that it is at most which is no stronger than we have for formula size.

8) Ah ha, that is a very good question, particularly as there isn’t any reason to think that that statement *can* be strengthened.

π Why do you say that?

8) Well, suppose that and depended on entirely different sets of variables. Then it is hard to see how to calculate more efficiently than calculating , calculating , and taking the max of the two. That gives an upper bound

π What? You mean it’s even *worse* than it is for ?

8) I think so. The trivial bound requires you to add 1.

I ought to say that the argument I’ve just given is another “obvious” argument that is not in fact known to be correct. I claimed that calculating the max of two functions that depend on disjoint sets of variables cannot be done more efficiently than the obvious way of doing it. But if that is really so, then one can obtain arbitrarily large linear lower bounds for circuit complexity as follows. Let be a small constant, and by brute force find a function that has circuit complexity at least Then let be copies of , each depending on a disjoint set of variables. Here, is Then the obvious straight-line computation of has length around , which is around However, the best known lower bound for circuit complexity is something like so I’m pretty sure that the result about functions depending on disjoint sets of variables is not known.

π What you’ve just said manages to be more irritating than one might have thought possible. I’m trying to say something about circuit complexity, and you have managed convince me not only that I can’t, but also that I won’t even be able to make rigorous the demonstration that I can’t.

8) Welcome to the wonderful world of unconditional results in theoretical computer science.

Hey, cheer up.

π¦

8) OK, let me try to say something to make you feel better. I want to point out that you’re not forced to define to be a number, and if you don’t then there’s a slightly better chance of proving something interesting.

π I feel better already. Tell me more.

8) I’d better warn you that what I’m about to say is less promising than it might at first seem. It’s still worth mentioning, but promise me you won’t get too excited about it. It’s a brilliant idea of Razborov, but he has also proved that it cannot be used to obtain interesting lower bounds for circuit complexity.

π What is it with this guy?

8) Well, I think like you he’d love to prove that PNP. But unlike you he has made (at least) two extraordinary contributions to the area: he has proved major results in the direction of the problem, and he has checked very very carefully that they cannot be pushed any further — indeed, he has proved this rigorously.

Anyhow, let’s not worry about that for now. I just want to show you that there is a different notion of formal complexity measure, where you allow it to take values that are *sets* rather than numbers.

To explain what I mean, let’s suppose that we have a function that associates with each Boolean function some set We are thinking of as being a measure of the complexity of , in some sense. What properties might have that could be useful? One obvious one is to insist that and are both contained in But that is not terribly helpful, because it implies that every is contained in the union So it looks as though can’t be bigger than times what it is for a basic function.

π Hang on. It seems to me that you are implicitly taking your sets to have some notion of size attached to them.

8) Yes I am. What I want is for to be small for basic functions and very large for some function in NP. And I also want it to grow only slowly when you do Boolean operations.

Here is a set of axioms that would be very useful to us if we could obtain them. The idea is to allow a small error on the right-hand side. That is, instead of asking for and to be contained in , we ask for them to be contained in where is a set of small measure. And to get things started, we’ll assume that whenever is plus or minus a basic function.

If that is the case, then what can we say about if it has small circuit complexity? Well, we have a sequence of functions , and for each we can find such that for some small set From this and a trivial inductive argument it follows that So if we can now show for some function in NP that is a set with measure that is larger than that of any set by a superpolynomial factor, then we have proved that cannot have polynomial circuit complexity.

π OK, I’ve got lots of questions about this, but here are just two to get started. How might one go about defining a useful set-theoretic complexity measure like this? And is there some trivial argument, as there is the case of formula complexity, that gives a kind of “maximal” set-theoretic complexity measure such that the size of is actually equal to the circuit complexity of ?

8) Let me deal with the first of these questions by telling you about Razborov’s method of approximations. The idea of this is to construct a lattice of Boolean functions, where all that this means is that you have the basic functions (and their negatives), together with some operations, and , under which is closed.

π Aren’t you going to assume *anything* about those operations? For example, shouldn’t they be associative?

8) Oddly enough, we don’t need to assume that, but if is to be of any use, then the operations will have to be chosen very carefully, as you’ll see.

Indeed, what we want from is two properties. We would like the operations and to *approximate* the operations and and we would also like to be as small as possible.

Now suppose that we have a straight-line computation If we carry out exactly the same computation but replacing the operations and by and then we obtain a sequence Now for each and let’s suppose that and except on a small set Then define to be the set for which equals or An easy inductive argument shows that agrees with except possibly on So we can set to be

π Something’s bothering me here. It’s that your function isn’t obviously well-defined. It seems to depend on the particular way that is computed.

8) You’re absolutely right of course. I must apologize. But it turns out that for some problems, one can prove highly non-trivial lower bounds using this kind of idea, though I have in fact oversimplified what Razborov did.

The bad news is that Razborov has proved that the method of approximations doesn’t yield even superlinear lower bounds for circuit complexity, unless you allow extra variables, in which case you can produce a suitable lattice in a trivial universal way.

π Ah, that’s sounding close to an answer to my second question. But perhaps we can think about it for ourselves.

Wait, there is indeed a spectacularly trivial set-theoretic complexity measure if it’s allowed to depend on how the function is computed.

π What’s that?

π You just take the set of all functions that you used in the computation. Then if say, then you’d have So the size of would be at most and it’s not hard to show that the size of is in fact the length of a computation closely related to the one given. (For uninteresting reasons it could be different, since and might both be less than but in that case would not have been used in the computation of )

I’m still interested to know whether there might exist a set-theoretic complexity measure that applies to functions rather than to computations of functions. Has Razborov shown that they cannot exist?

8) I’m not sure. What I can say is that his method of approximations doesn’t give you one. If you wanted it to do so then you’d have to find some way of associating with each a function that belonged to the lattice in such a way that was equal to and was equal to But that would be asking for a partition of that somehow respected Boolean operations. I’m basically certain that such a thing doesn’t exist. In fact, I think I’ve got a proof. If is small, then by the pigeonhole principle would have to be the same for a large set of functions But then you’d have two functions and that were almost orthogonal, from which it would follow that was nothing like either or but was equal to and

π I don’t think an additive combinatorialist would give up just yet.

8) What do you mean?

π Well, I can see that there is a problem with random functions if you want to define to be a Boolean function. But couldn’t one generalize the notion of a lattice to allow functions to take values other than and ? In additive combinatorics, one tends to think of a random function as being “just a random perturbation of the zero function”.

8) If you want to try something like that, then you’ve still got some serious thinking to do.

π Why?

8) Well, if you take two independent random Boolean functions and then is a random function as well, but it takes the value with probability instead of This suggests that if the zero function belongs to then should be the constant function But if and are *not* independent, then this is no longer appropriate. For instance, if , then is the constant function 1. So you can’t just send all random functions to the zero function and hope to preserve Boolean operations in a nice way.

π I see what you mean. That looks pretty bad. But does it show that no set-theoretic complexity measure that depends just on can exist? Or does it merely show that it cannot be derived from some lattice ?

8) I’m not sure. I’d be quite surprised if one existed. But perhaps it’s possible to find one in a trivial way.

π It’s difficult to see how one could define such a set without making any reference to circuits. So perhaps one would have to associate a set with each straight-line computation and then for each one would take the intersection of all the sets associated with computations of

π I’m not sure I like the sound of that. For instance, if you apply it to the “trivial” function that associates with each computation the set of Boolean functions involved in that computation, then you don’t get anything interesting when you intersect over all computations.

π Yes, you’re right. One would probably have to do something fairly clever.

It’s a very long shot, but I wonder whether the idea could somehow be converted into a set-theoretic complexity measure. For example — and I should quickly say that I do not for a moment expect this particular example to work — one could associate with each Boolean function the set of all Boolean functions such that is a witness to the fact that . That is, I’ve chosen that just because the sets get bigger when gets bigger. But I have no reason to suppose that anything much can be said about in terms of and

In fact, I can’t face thinking about it for now. I need a rest.

8) π OK, see you again some other time.

π But just to end on not too depressed a note, I’d like to point out that a property such as “The set of functions that witness that the dual norm of is at least 1 is not too large” is not completely obviously naturalizable. More generally, perhaps we can get somewhere by considering properties that are not in NP but in some class like #P (but probably not quite as extreme as that) where you have to recognise roughly how many ways that there are of checking that an NP property holds. We may manage to come up with some reason for this not working, but I think we’d have to think about it first.

October 16, 2009 at 8:00 pm |

Can’t do the latex, but there is a point about half way through where Rho(Fm) is used with “V” notation rather than “U” (Here is a set of axioms which would be very useful to us …)

And thank you for a cogent and interesting summary.

October 16, 2009 at 9:01 pm

Thanks very much — I’ve corrected it now.

October 16, 2009 at 9:27 pm |

You raise the following “direct product conjecture:” if has circuit complexity and has circuit complexity , is it the case that has circuit complexity ?

The intuition is that there should be no other way to compute than to first compute and , since the two are “independent.” This basic intuition is not necessarily true: take two operations such that is much easier to compute than and such that a distributive law applies.

Then computing is strictly easier than computing and then , because one can do the computation instead.

In fact I think that there are known counterexamples to the “direct product conjecture” above. Specifically (and this would apply to your candidate for a super-linear bound) if is any function, and , then the function

should always be computable in size at most . This contradicts the direct product conjecture if we pick to be a function of maximal circuit complexity .

Maybe someone who knows a bit more about circuit complexity can confirm? My idea would be to sort the input sequence using a sorting network realizable as a circuit of size . Next we say that given the truth-table of , and given a sorted sequence of inputs , there is a two-tape Turing machine that computes in time , and so it can be simulated by a circuit of size . Use this circuit, with the truth-table of hard-wired into it, to turn the sequence produced by the sorting network into the sequence . Now compute the OR of the above bit sequence

October 17, 2009 at 4:47 pm |

(I really hope this comes out right, because I haven’t tried WordPress Latex before.)

Luca: Yes, if the function has circuit complexity where is very high, then computing copies of can indeed have much lower circuit complexity than . A version of your idea is illustrated in Lemma 2 of

http://dspace.library.cornell.edu:8080/bitstream/1813/6996/1/75-215.pdf

which discusses these questions at length. (The above link is just an old tech report of Wolfgang Paul, but I can’t seem to find a free version of the published paper online.)

Tim: Suppose you find an infinite sequence of circuits (constructed randomly, or however you like) such that has circuit complexity at most polynomial in , and formula complexity that grows superpolynomially in .

Then there is an explicit polynomial time computable function that has superpolynomial formula complexity. Namely, the function which is iff the circuit described by on input outputs .

If has high formula complexity, then any circuit family which correctly computes must also have high formula complexity. Otherwise, I could just plug in the (polynomial length) code of each as input into the appropriate small formulas for , and now I have small formulas that compute .

So you do not need to worry if your circuits are inefficient to compute; in this case you get that for free.

October 17, 2009 at 5:39 pm |

Also, Chapter 10.2 of Ingo Wegener’s book “The Complexity of Boolean Functions” available at

http://eccc.uni-trier.de/resources/pdf/cobf.pdf

contains more information about this direct product stuff, which Wegener calls “mass production”.

October 19, 2009 at 5:51 am |

In a slightly different context (circuit and not formula complexity, multibit output) the canonical counterexample for the “direct sum” question (does copies of has circuit complexity times the circuit complexity of f) is fast matrix multiplication. (This has to do with Luca’s example of the distributive law.)

This example is in the case where we consider functions with multiple bits of output, and hence the operation is not OR but simple concatenation, where it seems “obvious” that you could not compute copies of the function on independent inputs without paying times the price.

But by simple counting you know that there is a linear function such that has circuit complexity (e.g., take to be computed by a random matrix), but if you look at the function that is defined as then this is just multiplying the matrix by the matrix and can be done in time.

October 19, 2009 at 5:54 am |

p.s. I learned from Avi Wigderson that one should use “direct sum” for questions of this form (does the amount of resources grow when combining functions) and “direct product” to questions of the form: “does the probability of successfully computing the function decreases exponentially when combining functions”

October 20, 2009 at 12:14 am |

This reminds me of a chess book I once read. There was an analysis of a chess game as I recall. There were several participants in a dialog involvign various features of chess analysis. The use of emoticons also reminds me of the ongoing project of translating Moby Dick into Japanese emoticons. Today was the deadline for the raising of the 3500 dollars needed and apparently they have reached their goal:

Also on this survey article:

http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

There is a mention of Geometric complexity theory. So apparently there is an approach using complexity that works although the authors say it may take one hundred years to reach an answer. There is this reference:

Mulmuley, K. and Sohoni, M. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM Journal on Computing 31, 2, (2001) 496β526.