State of circuit lower bounds now slightly less humiliating
When people want to emphasize how pathetically far we are from proving P≠NP, they often use the following argument: for godsakes, we can’t even prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates!
But no more.
As some of you may have heard, recently Ryan Williams achieved a breakthrough in circuit lower bounds. And as a result, now we can prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates.
More generally, Williams proves that NEXP does not have ACC circuits of third-exponential size: that is, size f(n) where f(f(f(n))) is exponential. Here NEXP means nondeterministic exponential time (the exponential-time analogue of NP), and was long a “barrier class” for circuit lower bounds. (Note that, if we go even slightly above NEXP, to MAEXP, then Buhrman, Fortnow, and Thierauf proved in 1998 that MAEXP doesn’t have polynomial-size circuits of any depth, and here the polynomial can be improved to half-exponential.) Meanwhile, by “ACC circuits” we mean a nonuniform family of constant-depth circuits consisting of AND, OR, NOT, and MOD m gates for arbitrary positive integers m. ACC is another “barrier class” for circuit lower bounds: if we go even slightly below it, to AC0[p] (the same as ACC, except that now we only allow MOD p gates for some fixed prime p), then we’ve known how to prove exponential circuit-size lower bounds since the work of Razborov and Smolensky in the 1980s.
To achieve the combination of NEXP and ACC, Williams implements a program proposed in his previous STOC’2010 paper, for the specific case of ACC. At the core of his lower bound is an algorithm for deciding satisfiability of ACC circuits, which does slightly (not much) better than brute-force search. (The algorithm relies on, of all things, fast multiplication of rectangular matrices.) While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”
I haven’t verified Williams’s proof, but the high-level ideas are compelling—and while the result is one of the most spectacular of the decade, it’s not so far beyond the current frontier as to strain credulity. Suffice it to say that I won’t be betting $200,000 against this one.
Congratulations, Ryan!
Update: Amusingly, if you google Ryan Williams ACC, you get a football player of the same name who was apparently Rookie of the Year in the Atlantic Coast Conference. Let’s all link to Ryan’s paper from our homepages, and see if we can make our “ACC Rookie of the Year” win out!
Follow
Comment #1 November 8th, 2010 at 2:09 pm
And I bet he typeset his result in LaTeX too…
Comment #2 November 8th, 2010 at 2:11 pm
Indeed he did 😉
Comment #3 November 8th, 2010 at 2:44 pm
And as luck would have it he is on the job market this year! Need any more complexity theorists at MIT?
Comment #4 November 8th, 2010 at 3:19 pm
Jill: Personally, I think it’s obvious that any department that gets Ryan and Virgi will have scored a coup.
But I’d like to issue a polite request to refrain from further job-market discussion on this thread. Even if they start out with good intentions, comment threads about the academic job market have shown a reliable, Godwin-like tendency to turn nasty and trample on people’s privacy.
Comment #5 November 8th, 2010 at 4:09 pm
What exactly is third-exponential size? Could you give an example function?
Comment #6 November 8th, 2010 at 4:15 pm
NCLM: As I said, “third-exponential” means a function f such that f(f(f(n))) grows like 2n. Unfortunately, while such functions can be proved to exist, they don’t have any closed form in terms of familiar functions like exp, log, etc. — otherwise, I would’ve used the closed form! 🙂
These sorts of functions (more typically “half-exponential,” meaning that f(f(n)) grows like 2n) have come up before in circuit lower bounds. In fact, I had a whole comment thread about them a few years back.
Comment #7 November 8th, 2010 at 5:55 pm
Scott, is there a function expressible in closed form using the familiar functions which is between third-exponential and half-exponential?
Can we prove that NEXP-complete problems aren’t solvable by logarithmic depth, polynomial-size circuits consisting entirely of mod 6 gates, or is that another huge hurdle?
Does this result cross some relativization/naturalization/algebrization barrier, or is it still below those?
Comment #8 November 8th, 2010 at 6:07 pm
Bram:
is there a function expressible in closed form using the familiar functions which is between third-exponential and half-exponential?
I doubt it—but alas, I don’t know how to prove that any such function is not expressible in closed form. This is what I was asking about in that thread from years ago, and I never got an answer. Maybe I’ll post the question to MathOverflow!
Can we prove that NEXP-complete problems aren’t solvable by logarithmic depth, polynomial-size circuits consisting entirely of mod 6 gates, or is that another huge hurdle?
Another huge hurdle.
Does this result cross some relativization/naturalization/algebrization barrier, or is it still below those?
Yes, I think it crosses the relativization and algebrization barriers, in the sense that one can construct an oracle A relative to which NEXPA ⊆ ACCA, and even NEXP~A ⊆ ACCA (this should follow from trivial modifications to the NEXP~A ⊆ PA/poly oracle from my paper with Wigderson).
As for the natural proofs barrier, the issue is that we don’t currently have a good candidate for a pseudorandom function family (PRFF) computable by ACC circuits. Indeed, maybe Ryan’s new algorithm for ACC circuit satisfiability could be used to show that no such PRFF can be “maximally hard to break”! On the other hand, if there is a natural proofs barrier for ACC, then Ryan’s proof certainly gets around it—which would be no great surprise, since the proof ultimately relies on a time hierarchy theorem, and time hierarchy theorems are the “original” non-naturalizing lower bounds!
Comment #9 November 9th, 2010 at 12:34 am
One of the most spectacular of WHICH decade? 2001-2010 I guess? Just making sure. 🙂
NCLM and Bram: http://en.wikipedia.org/wiki/Functional_square_root says a little bit.
Comment #10 November 9th, 2010 at 5:48 am
asdf: Yeah, I meant the preceding decade, which is the one I know somewhat more about. Here’s hoping that complexity theory (and esp. circuit lower bounds) in the next decade will surpass this result!
Comment #11 November 9th, 2010 at 9:58 am
Scott wrote:
‘The algorithm relies on, of all things, fast multiplication of rectangular matrices… While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”’
There may be more than a philosophical connection! Geometric methods have already been employed to study the complexity of matrix multiplication (arxiv:cs/0703059), and GCT specifically is just beginning to be used there (arxiv:1011.1350).
Comment #12 November 9th, 2010 at 1:38 pm
As an outsider to complexity theory who can more or less understand the statement in William’s result (but far from
being able to understand the proof) –
if you define a metric where 1 is the size of a breakthrough
on the order of William’s, and the distance X is the number of breakthroughs of similar magnitude required to get from state of knowledge A to state of knowledge B (say each of them have a different known lower bound) – what is the distance X from our current state of knowledge to figuring out if P≠NP?
Comment #13 November 9th, 2010 at 1:43 pm
oz: 587.
Comment #14 November 9th, 2010 at 3:46 pm
Scott: I’m not sure my question was worded clearly – Do you know of an ordinary function which is asymptotically greater than third exponential but asymptotically less than half exponential?
The lack of difficult functions in ACC confuses me. Aren’t these the sorts of things which block ciphers are generally made out of? You can even cheat a bit and do diffusion using gates with large fan-in. Then again, the number of rounds of a black cipher is generally significant, so maybe that’s where the log(n) sneaks in. Maybe Williams’s new technique could be applicable to breaking ciphers. If block ciphers really are just barely not possible in ACC, than next barrier is a real doozy.
Since you say that this is the biggest result since at least 2000, and that there are 587 left to go, does that mean that you think it will be at least 5870 * 11 = 64570 years until we can prove that P != NP?
Comment #15 November 9th, 2010 at 3:46 pm
sorry, I meant 587 * 11 = 6457 years, dunno how that typo happened
Comment #16 November 9th, 2010 at 6:27 pm
Good news, everyone!
I posted the question to MathOverflow of whether one can prove that there’s no closed-form formula (using the operations +, -, *, /, exp, and log) for a function f such that f(f(n)) grows exponentially. I got an immediate positive answer from Gerald Edgar. Note that this result also holds for third-exponential functions, etc., as well as (for example) anything sandwiched between third- and half-exponential.
So we have an answer to Bram’s question above: no, there are no “natural” functions with any of these growth rates—at least if by “natural”, you mean definable by composing various functions with “ordinary” growth rates!
Comment #17 November 9th, 2010 at 6:35 pm
There really is a giant no man’s land between polynomial and exponential!
Comment #18 November 9th, 2010 at 6:36 pm
Bram, to address your other question: we don’t know whether or not there are good pseudorandom functions in ACC. (By contrast, if you just wanted pseudorandom generators, which stretch the seed by a polynomial rather than an exponential amount, then we can certainly get that in ACC, and even in much smaller classes like NC0.)
Especially in the wake of Ryan’s result, the question of whether ACC has pseudorandom functions seems extremely well worth answering. The answer will determine whether (a) Ryan’s lower bound circumvents the Natural Proofs barrier, or (b) ACC never had a Natural Proofs barrier to begin with.
(In other words, this problem is sort of like figuring out whether the front door was locked, after the barbarians have already stormed the castle… 🙂 )
Comment #19 November 9th, 2010 at 6:54 pm
A sub-exponential algorithm for figuring out if an ACC circuit is satisfiable would be quite a surprising result!
Comment #20 November 9th, 2010 at 11:54 pm
Google for: Ryan Williams acc0
It seems that dropping that 0 has a significant effect and we should keep it even if it does not make sense. 😉
Comment #21 November 9th, 2010 at 11:57 pm
The Wikipedia page for Ryan Williams should be updated, otherwise I am not optimistic that we can change the ranking by linking to Ryan’s page.
Comment #22 November 10th, 2010 at 3:23 am
Re: Half exponential in closed form.
A solution in closed form means exactly that it is expressible in terms of some function that has a name, nothing more or less. If the name has some tradition, or appears in a book or list, so much the better. Back in the day, this meant it was covered in, say, Abramowitz & Stegun, or maybe Magnus & Oberhettinger. Nowadays, maybe being in MS Excel, or the Boost C++ special functions package, or Mathematica, or maybe if Google evaluates it, resonates.
With no further ado, I hereby define a sequence of “fractional exponential” functions by the functional equations
e(1, x) = 2^x,
e(2, e(2, x)) = 2^x,
e(3, e(3, e(3, x))) = 2^x,
e(4, e(4, e(4, e(4, x)))) = 2^x,
and so on.
If you put your pure mathematician hat on, figure out if these are defined uniquely.
If you put your applied mathematician hat on, figure out some properties of these functions. For example,
e'(2, x) = ln 2 e(1, x) / e'(2, e(2, x)).
That is a start. You are on your own now.
As I recall, when Scott asked about e(2,x) a few years ago, I figured out some properties. I don’t recall if I sent them in.
BTW, M&E is still selling for about $50 on Amazon. I have one up in the attic. A&S now has an improved online version at http://dlmf.nist.gov/ Check it out! As with the Ackermann function, as a matter of principal everyone should know a little bit about the Riemann Zeta function.
Comment #23 November 10th, 2010 at 2:28 pm
Raoul, those aren’t satisfactory answers. When people want closed form functions they generally are asking for an elementary function.
Comment #24 November 10th, 2010 at 4:56 pm
How far away is the community now from proving $ P \ne NP$. Is any kind of proof visible at this stage?
Comment #25 November 10th, 2010 at 5:07 pm
Is any kind of proof visible at this stage?
No. Only shadows of shadows.
Comment #26 November 10th, 2010 at 8:33 pm
Hi,
I think that one critical point in Ryan’s beautiful work is not emphasized enough: In order to apply Ryan’s technique, you don’t need a (weak) algorithm for deciding circuit satisfiability, but rather a (weak) algorithm for distinguishing an unsatisfiable circuit from a circuit that is satisfied by at least half of its assignments.
Note that the latter distinguishing problem is easily solvable within RP, and the point is that Ryan’s technique requires a weak *deterministic* algorithm.
This fact is important for two reasons:
1. It makes Ryan’s technique much stronger and more applicable, since it is much more plausible to find weak deterministic algorithms for an RP problem than to an NP-complete one (i.e. Circuit-Sat).
2. More conceptually, I believe that Ryan’s technique should be viewed as a very powerful instance of the family of “derandomization implies circuit lower bounds” results. Perhaps other techniques from this family can be combined with Ryan’s work to obtain even stronger results.
Comment #27 November 10th, 2010 at 8:43 pm
Joshua,
Functions are generally classified as:
1. Elementary: What you wind up with if you start with polynomials, exponentials, and logs, and apply +, -, *, /, and root finitely many times. These are in a standard calculus book.
2. Algebraic: Satisfies a polynomial equation, whose coefficients are polynomials in x (the independent variable).
3. Transcendental: Not algebraic. Note that some elementary functions are Algebraic (polynomials, rationals, fractional powers), and some Transcendental (trig, logs, irrational powers).
4. Higher Transcendental: Many references (29 hits on Amazon) have this title. Usually the gamma function is regarded as the “lowest of the higher transcendental” functions, and is Chapter 1.
5. Functions of Mathematical Physics and/or Special functions (441 hits on Amazon): A subset of the Higher Transcendentals that turn up a lot in physics, usually as a result of using separation of variables on the wave, potential, and heat equation in two or three dimensions.
6. Hypergeometric (possibly generalized and/or confluent). An astounding fraction of important functions fit into a simple framework created by Gauss. If you work with them, everything falls into place, and you realize what a sharp guy Gauss was.
Over 100 years ago it was realized that most solutions to ordinary differential equations do not fall into any category of of known functions. All you can do is name the solution, and set to work figuring out some properties and working out suitable approximations. You can do a good job at this; last week a space probe zipped past and photographed a comet that looks like a bowling pin. It was not an accident that it was near by, it was engineers approximating differential equations.
The only thing you know about the half exponential function is that f(f(x)) = 2^x. This probably does not define it uniquely. A pure math question is how smooth a solution there is. At any rate, this is a hard equation to learn much from, and it is a good bet that the solution will be “more transcendental” that the solutions you get from simple differential equations.
So, the likelihood that there is an “elementary solution” is pretty close to 0.0. That just means it is time to figure out some properties. A few power series coefficients at x=0 would be interesting. For TCS purposes, an decent approximation for large x would be almost as good as an explicit formula. For example, a reasonably simple pair of functions g and h such that for large x:
x WLT g(x) LT f(x) LT h(x) WLT 2^x,
(WLT = Way Less Than, LT = Less Than)
would be useful.
Comment #28 November 11th, 2010 at 1:21 am
Raoul, yes, thank you I knew that. Note that in his post on Math Overflow, Scott apparently interpreted closed form essentially as I did.
Comment #29 November 11th, 2010 at 11:57 am
Just wanted to point out to everyone that there is a typo in Scott’s answer of 587 above. He forgot the exponent, the right answer is 10^587…. 🙂
(not taking anything away from Ryan, but rather to give to a different problem)
Comment #30 November 11th, 2010 at 5:27 pm
How about a closed form function that shares some key aspects of a half exponential? Perhaps a simple function f(x) that is is subexponential (i.e., limit f(x) / 2^bx = 0 for any b>0, limit is at infinity) and also limit f(f(x)) / 2^x is greater than 1.
The simplest one I could come up with is
f(x,a) = x^(x^a) for any a in (0,1).
g(x) = x^(lg x) does not work, because g(g(x)) is still subexponential, in fact x^(lg x)^3.
Comment #31 November 12th, 2010 at 12:39 am
Switching from x to n for the variable, we look for the half exponential h(n), defined by h(h(n)) = 2^n.
Recall that exponent towers are evaluated from the top down, thus
g(n) = n^(lg n) = 2^(lg n)^2,
g(g(n)) = 2^(lg n)^2^2,
and in general an m-times iterated g(n) is given by
g(g(g( ….g(n)…) = 2^(lg n)^2^m = n^(lg n)^(2^m -1).
It is pretty surprising to find a simple expression for an iterated function!
However,
2^(lg n)^p and n^(lg n)^p
are subexponential for any power p, as can be seen by dividing by 2^dn for any positive d, so this family of functions is too small to contain h(n).
If h(n) is written as h(n) = n^k(n), the above results show that
(lg n)^p for any p is a lower bound and n^a is an upper bound for any positive a, giving hope of finding a k(n) that somehow interpolates between (lg n)^p and n^a. Means and geometric means do not work in the n go to infinity limit.
If I get some time and a pot of ultra strength coffee this weekend, I am going to try the family
k(n,b,c) = n^(b/n^c) for positive b and c.
The idea is to be less than n^a in the limit. If there are values of b and c such that h(n,b,c)= n^k(n,b,c) is subexponential, but h(h(n,b,c),b,c) is exponential, we would be pretty close to pinning down h(n).
First I need to work out the algebra of exponent towers.
Comment #32 November 15th, 2010 at 7:23 am
To matt: the proof for P ne NP would be 587 times as long as the current ones, but finding it requires 10^587 times as much computation.
Comment #33 November 24th, 2010 at 10:02 pm
Basic question: Reading about this, some places I’ve seen ACC defined so that each circuit can only use mod m gates for a fixed integer m; other places have not mentioned any restriction against using different moduli in the same circuit. So – is the latter equivalent to the former? If not, is the latter something that’s been studied at all?
Comment #34 December 30th, 2015 at 11:30 pm
Do we know $NP$ is not in $ACC0$? If $NP$ is in $P/poly$ but the circuit needs to be only of $ACC0$ structure would that mean $NP$ is in $P/poly$ as well?