Within the last week and a half, I saw two movies that rank among the best I’ve ever seen: Slumdog Millionaire and Defiance. Slumdog, as you probably know by now, is about an orphan from Mumbai who, in the process of fleeing starvation, murder, and the gouging out of his eyes, picks up enough trivia to go on the Indian version of “Who Wants To Be A Millionaire” and answer almost every question correctly. (It’s about 100 times better than the premise makes it sound.) Defiance tells the true story of the Bielski brothers in Belorussia (where most of my family is from), who fled to the forest when the Jews were rounded up in December 1941, and eventually organized the largest Jewish resistance operation of the war.
On thinking it over, I was surprised to realize I liked these two seemingly-unrelated movies for the same reasons. Let me try to break down what made them good:
Both draw their emotional punch from reality. Almost everything in Defiance happened. Slumdog, while fictional, is (amazingly) the first Western blockbuster I can think of about modern India—a place where 21st-century communication, entertainment, and industry coexist with 16th-century squalor, and everyone acts as if that’s normal. (If you haven’t been there, the anarchic street scenes might strike you as obviously exaggerated for effect. They aren’t.)
Both tell wildly-improbable tales of bare physical survival. Survival stories aren’t just the best for keeping you in your seat: they also provide a useful reminder that your beliefs about politics and human nature might be badly distorted by the contingent facts that you have enough to eat and that armed thugs aren’t trying to kill you. (I tried to think of a phrase to summarize my political philosophy, and came up with “liberal pessimist pragmatist rationalist of an unsentimental kind.” Slumdog and Defiance both explain this concept better than I could.)
Even as they starve, sleep in the rain, and flee their would-be killers, the protagonists in both movies pursue goals beyond just staying alive—which is what lets us identify with them so strongly. Jamal Malik appears on a game show to win the beautiful Latika. Tuvia Bielski risks his life to exact revenge on the police officer who killed his parents. Days after losing their families to the Nazis, the young women who arrive at the Bielski settlement are weighing which of the men to offer themselves to as “forest wives.”
Both movies use visuals in the service of a story rather than vice versa. When Spielberg filmed Schindler’s List in black and white (save for the famous girl in red), reviewers were full of praise: what a profound artistic statement he must’ve been making! The result, though, was that people saw the Holocaust the same way they’d seen it everywhere else: as something from some remote, incomprehensible black-and-white past. But Defiance, like The Pianist, denies you the luxury of a visual remove—as if to say, “this is how it was. It’s part of the same universe you live in right now. It’s not even particularly incomprehensible, if you choose to comprehend it.”
Both movies indulge the audience in what it already knows about the respective cultures. Slumdog features hilarious scenes at the Taj Mahal and a call center, and ends with a tongue-in-cheek Bollywood dance number. Defiance portrays the “malbushim” (the Bielskis’ derisive term for intellectuals) arguing and quoting Talmud as they starve in the woods. It’s as if, instead of telling you that the stereotypes you came in with are false, these movies say “and so what if they’re true?”
Both movies have been criticized as “simplistic”—a word that seems to mean “too clear or comprehensible for polite company,” and that I’ve found to be an almost-perfect marker for things that I’m going to like or agree with. Even as the plots add on layers of complexity—sibling rivalries, uneasy alliances, unconsummated love—the dialogue is always straightforward enough that even a borderline Aspberger’s case like myself could follow what was going on without difficulty.
Despite a backdrop of blood and tears on a continent-wide scale—which the audience knows full well is real, not fictional—both movies end up joyous and uplifting. Lots of bad guys get blown to pieces, while the good guys you most care about live. Is such uplift “glib,” “problematic,” or even “simplistic”? Well, what’s the point of going to a movie in the first place? I want to walk away feeling that the inherent injustice of the universe can be successfully defied, that I need not apologize for taking comparatively benign steps to solve the comparatively trivial problems in my own life. I want my $10’s worth.
As MIT grad student Jelani Nelson rightly pointed out to me, an historic world event took place on Tuesday, January 20—an event that many of us have awaited for decades, one that we thought we’d never live to see—and I inexcusably failed my readers by neglecting to blog about it. The event in question, as everyone knows, was Mark Braverman posting to his web page what looks to be a proof of the Linial-Nisan Conjecture. The LN conjecture, posed in 1990, held that
Alright, let me try again in English. The conjecture says that no logic circuit, composed of a polynomial number of AND, OR, and NOT gates (of unbounded fan-in) arranged in a constant number of layers, can distinguish n input bits x1,…,xn that are truly random, from n input bits that look random on every subset of (say) n0.001 bits, but that could be correlated in arbitrary ways across larger scales. In other words, if such a circuit accepts truly random bits with probability close to 1, then it also accepts the pseudorandom bits with probability close to 1, and vice versa. If you want to distinguish the random bits from the pseudorandom bits with noticeable bias, then you need a more powerful kind of circuit: either greater depth (say, log(n) layers instead of O(1)), or more gates (say, exponentially many), or more powerful gates (say, XOR or MAJORITY gates instead of just AND, OR, and NOT). To a constant-depth, polynomial-size, AND/OR/NOT circuit (which we call an AC0 circuit for short—don’t ask why), local randomness looks just the same as global randomness. Or so says the Linial-Nisan Conjecture.
Now, we’ve known since the eighties that AC0 circuits have serious limitations. In particular, we’ve known lots of specific pseudorandom distributions that fool them. What Linial and Nisan conjectured, and Braverman appears to have proved, is that any distribution will do the job, just so long as it “looks random locally.”
A year and a half ago, Bazzi proved the Linial-Nisan conjecture in the special case of depth-two circuits, in a 64-page tour de force. Then Razborov gave an essentially 2-page proof of the same result. (Need I explain how awesome that is?) Braverman extends Bazzi’s result to circuits of any constant depth; his proof is almost as short as Razborov’s.
In proving these lower bounds, the name of the game is the polynomial method (the subject of my FOCS tutorial). Given an AC0 circuit C, you first construct a low-degree real polynomial that approximates C pretty well on most inputs. (How do you construct such a thing? And what does “pretty well” mean? Save it for the comments section.) Then you observe that no low-degree polynomial could possibly distinguish a random string from a string that only looks random locally. Why? Because a low-degree polynomial, by definition, is a sum of local terms, and if none of those individual terms can distinguish truly random bits from pseudorandom ones (as was assumed), then their sum can’t distinguish them either, by the deep principle of the universe we call linearity of expectation. (By contrast, an AND or OR of terms could in principle detect “global” properties of the input that none of the individual terms detected—which is why we couldn’t just apply such an argument to the AC0 circuit directly.) It follows, then, that the original circuit couldn’t have distinguished local randomness from global randomness very well either, which is what we wanted to show.
So everything boils down to constructing these low-degree approximating polynomials and proving they have the right properties. And in that context, what Braverman does is almost hilariously simple. Given an AC0 circuit C, he first constructs a low-degree polynomial p that agrees with C on most inputs (from whatever fixed probability distribution you want), using the celebrated method of Valiant-Vazirani and Razborov-Smolensky. He then observes that, when p fails to agree with C, there’s another AC0 circuit E, of depth slightly greater than C, that detects the failure. Next he finds a low-degree polynomial q that approximates E in L2-norm, using the also-celebrated 1993 theorem of Linial-Mansour-Nisan. Then he looks at p(1-q), and shows that it’s a polynomial that usually agrees with C, but when it does disagree, usually isn’t too far off. And then … well, at that point he’s really almost done.
While I had no involvement whatsoever with this beautiful result, I’m pleased to have unwittingly set in motion a chain of events that led to it. Since the summer, I’ve been trying to get as many lowerbounderati as possible interested in BQP versus PH, a central open problem of quantum complexity theory that’s resisted progress since the prehistoric days of 1993. (There are certain problems that I mentally classify as “rabbits,” after the Killer Rabbit of Caerbannog from Monty Python and the Holy Grail. BQP vs. PH is one of the fluffiest, most adorable rabbits ever to leap for my throat.)
Concretely, the goal has been to construct an oracle relative to which BQP (Bounded-Error Quantum Polynomial-time, the class of problems that are feasible for a quantum computer) is not contained in PH (the Polynomial-time Hierarchy, a generalization of NP). Such a separation would give us probably our best evidence to date that BQP is not contained in NP—or loosely speaking, that not only can quantum computers solve certain problems exponentially faster than classical ones, they can solve certain problems exponentially faster than classical computers can even verify the answers.
(NerdNote: We do have oracles relative to which BQP⊄NP, and indeed BQP⊄MA. But we still don’t have an oracle relative to which BQP⊄AM. And that sticks in the craw, since we know that AM=NP under a derandomization hypothesis.)
Now, it occurred to me that BQP versus PH is closely related to the Linial-Nisan Conjecture. That’s not quite as surprising as it sounds, since you can think of PH as the “exponentially scaled-up version” of AC0 … so that fighting PH ultimately boils down to fighting AC0.
Alright, so consider the following problem, which we’ll call Fourier Checking. You’re given black-box access to two Boolean functions f,g:{-1,1}n→{-1,1}, and are promised that either
f and g were both generated uniformly at random (independently of each other), or
f and g were generated by first choosing a random 2n-dimensional unit vector v, then setting f(x)=sgn(vx) and g(x)=sgn((Hv)x), where H represents the Fourier transform over Z2n.
The problem is to decide which, with small probability of error.
It’s not hard to see that Fourier Checking is in BQP (i.e., is efficiently solvable by a quantum computer). For to solve it, you just go into a uniform superposition over all x∈{-1,1}n, then query f, apply a Quantum Fourier Transform, query g, and see if you’re left with (1) random garbage or (2) something close to the uniform superposition that you started with.
On the other hand, one can show that:
A certain generalization of Bazzi’s Theorem (from “local randomness” to “local almost-randomness”—as usual, ask in the comments section) would imply that Fourier Checking is not in an important subclass of PH called AM (for “Arthur-Merlin”). And thus, we’d get an oracle relative to which BQP⊄AM.
The analogous generalization of the full Linial-Nisan Conjecture would imply that Fourier Checking is not in PH. And thus, we’d get our long-sought oracle relative to which BQP⊄PH.
After realizing the above, I tried for months to prove the requisite generalization of Bazzi’s Theorem—or better yet, get someone else to prove it for me. But I failed. All I managed to do was to goad Razborov into proving his amazing 2-page version of Bazzi’s original theorem, which in turn inspired Braverman to shoot for the full Linial-Nisan Conjecture.
In what appears to be a cosmic prank, about the only conjectures in this area that still haven’t been proved are the ones I needed for the quantum computing problem. And thus, I will offer $100 for a proof that Fourier Checking is not in AM, $200 for a proof that it’s not in PH. In so doing, my hope is to make Tuesday, January 20, 2009 remembered by all as the day our economy finally got back on track.
In response to my (justified) kvetching about Vista in my last post, a commenter named Matt wrote in:
I hear there’s some free operating system written by a guy from Finland. Sounds pretty crazy to me, but I hear you can just download it for free. Maybe you could have used that if you didn’t like Vista?
Yes, I’ve heard of the OS by the guy from Finland, and even tried it. On introspection, though, my feelings about Windows are pretty much identical to my feelings about America: sure, it’s big and bloated and crass and flawed and overcommercialized and buggy and insecure, and at least 95% of the insults that the sophisticates hurl at it are true. And other countries and OSes have a great deal to be said for them, and indeed I do spend much of my time visiting them. But this is home, dammit, it’s where I was brought up, and things would have to get a lot worse before I’d consider moving away for good.
All I need, then, is the Windows analogue of Obama. Would that be the Windows 7 beta? (Vista, of course, being the Windows analogue of Bush?)
I’ve been suffering from terrible bronchitis for two weeks. I can barely talk. I had to cancel a planned colloquium. I’m not even gonna try to describe what I’ve been coughing up. The doctor couldn’t figure out if it was viral or bacterial, but gave me antibiotics anyway.
My laptop broke, the day before I had to give my time travel talk at QIP’2009 in Santa Fe (if you want to know what actually happened at the conference, see Dave’s blog or ask in the comments section). First the fan started acting up—causing the machine to overheat and shut itself off whenever the computations got too complex; then the ‘G’ and ‘H’ keys became unreliable; and finally the hard disk went, taking much of my data along with it (though I recovered the most important stuff). So I ran out and bought a new Toshiba laptop, which of course came preinstalled with Vista, which is not just said by everyone to suck but truly does suck. (Though if you spend a day disabling all the new features, you can make it almost like XP.)
On the flight back to Boston from Santa Fe, the pressure drop during the descent, combined with my bronchitis, sent my ears into pain for days.
The shitty economy is no longer just an abstraction, as friends and close family members have lost their jobs. I, the starving quantum complexity theorist, now feel like one of the last people I know with an income. (Though MIT, like other universities, has lost much of its endowment and now faces serious hardships as well.)
But it’s all OK, because the competent guy is president now—even if he flubbed his Oath of Office (update: it seems most of the fault lies with Roberts (another update:Steven Pinker theorizes that the problem was Roberts’s reluctance to split an infinitive)). He’s gonna fix everything. Just give him a day or two.
The mathematicians discovered the central mystery of computability, the conjecture represented by the statement P is not equal to NP. The conjecture asserts that there exist mathematical problems which can be quickly solved in individual cases but cannot be solved by a quick algorithm applicable to all cases. The most famous example of such a problem is the traveling salesman problem, which is to find the shortest route for a salesman visiting a set of cities, knowing the distance between each pair. All the experts believe that the conjecture is true, and that the traveling salesman problem is an example of a problem that is P but not NP. But nobody has even a glimmer of an idea how to prove it. This is a mystery that could not even have been formulated within the nineteenth-century mathematical universe of Hermann Weyl.
At a literal level, the above passage contains several howlers (I’ll leave it to commenters to point them out), but at a “deeper” “poetic” level, Dyson happens to be absolutely right: P versus NP is the example par excellence of a mathematical mystery that human beings lacked the language even to express until very recently in our history.
Speaking of P versus NP, I’m currently visiting Sasha Razborov at his new home, the University of Chicago. (Yesterday we had lunch at “Barack’s favorite pizza place”, and walked past “Barack’s favorite bookstore.” Were they really his favorites? At a deeper poetic level, sure.)
One of the highlights of my trip was meeting Ketan Mulmuley for the first time, and talking with him about his geometric approach to the P vs. NP problem. Ketan comes across in person as an almost mythological figure, like a man who flew too close to the sun and was driven nearly to ecstatic obsession by what he saw. This is someone who’ll explain to anyone in earshot, for as long as he or she cares to listen, that he’s glimpsed the outlines of a solution of the P vs. NP problem in the far frontiers of mathematics, and it is beautiful, and it is elegant—someone who leaps from Ramanujan graphs to quantum groups to the Riemann Hypothesis over finite fields to circuit lower bounds in the space of a single sentence, as his hapless listener struggles to hold on by a fingernail—someone whose ideas seem to remain obstinately in limbo between incoherence and profundity, making just enough sense that you keep listening to them.
Now, I get emails every few months from people claiming to have proved P≠NP (not even counting the P=NP claimants). Without exception, they turn out to be hunting polar bears in the Sahara: they don’t even grapple with natural proofs, or relativization, or algebrization, or the lower bounds/derandomization connection, or any the other stuff we know already about why the problem is hard. Ketan, by contrast, might be searching for polar bears with a kaleidoscope and trying to hunt them with a feather, but he’s in the Arctic all right. I have no idea whether his program will succeed within my lifetime at uncovering any of the truth about the P vs. NP problem, but it at least clears the lower hurdle of reflecting some of the higher truth.
1. The CRA’s Computing Community Consortium, chaired by national treasure Ed Lasowska of the University of Washington, recently put up a website with fifteen brief essays about “Computing Research Initiatives for the 21st Century.” These essays will apparently be reviewed by the science policy staff at the Obama transition office. Dave Bacon and I wrote the essay on quantum computing—or rather, Dave wrote it with his inimitable enthusiasm, and then I tried in vain to moderate it slightly. (When Dave told me that President-elect Obama needed my help with quantum computing policy, what was I going to say? “Sorry, I’m doing my laundry this weekend”?)
2. Lee Gomes of Forbes magazine wrote a fun article about the Worldview Manager project that I blogged about a while ago. (For some reason, Lee wasn’t deterred by my pointing out to him that the project hasn’t even started yet.)
Whereas nerds stand to benefit, even more than normal people, from becoming more assertive, outgoing, optimistic, obamalike in temperament, and all those other good things,
Whereas the fundamental problem with nerds is that they’re constantly overthinking everything,
Whereas this means nerds are regularly beaten in life by people who think less than they do,
Whereas it also means that nerds can’t read self-help books without coming up with dozens of (generally sound) reasons why everything they’re reading is a load of crap,
Whereas there’s therefore a large unmet need for self-esteem-boosting, personality-improving materials that would somehow fly under nerds’ radar, disarming the rational skeptical parts of their brains,
This holiday season, as my present to all my nerd readers, I’ve decided to start an occasional series entitled Nerd Self-Help.
Today’s installment: What should you do when you find yourself asking whether you have any “right to exist”?
Pondering the problem this morning, I hit upon a solution: Ask yourself whether the integer 8 has any right to exist.
In first-order logic, existence is not even a property that can be predicated of objects. Given a universe of objects, you can ask about properties of those objects: for example, is there a perfect cube which is one less than a perfect square? But it’s simply assumed that when you use a phrase like “is there,” you’re quantifying over everything that exists. (As many of you know, this was the basic insight behind Kant’s refutation of Anselm’s ontological proof of the existence of God: the notion of “a being that wouldn’t be perfect without the added perfection of existence,” said Kant, is gobbledygook.)
Similarly, I claim that if you were to formulate a theory of human rights in first-order logic in any “natural” way, then whether you have a right to exist is not even a question that would arise within that theory. Such a theory might include your right to not be murdered, to get a fair trial, to engage in consensual sexual activities, to own property, etc., but not your “right to exist”: that “right,” to the extent it even made sense, would simply be presupposed by your being part of the universe of persons that the theory of rights was quantifying over. In other words, the sequence of words “do I have the right to exist?” seems to me to dissolve on analysis, an ill-formed non-question.
Now, I don’t doubt that there are plenty of logical, metaphysical, and legal objections that might be raised against the above argument. But here’s the key: don’t think about it too much! Just trust that there’s a rational-sounding argument for why you shouldn’t doubt your right to exist, and be happy.
The above question came up in conversation with Michael Vassar and some other nerds in New York City yesterday (before I went with relatives to see Gimpel Tam, an extraordinarily dark and depressing musical performed entirely in Yiddish). Look, I know a massive black hole would swallow the earth extremely quickly, and I also know that a microscopic black hole would quickly evaporate as Hawking radiation. So suppose we chose one of intermediate size so as to maximize the earth’s survival time—how long a time could we achieve? (Does the answer depend on the viscosity of the magma or whatever else is in the earth’s core?) Sure, I could try to calculate an answer myself, but why bother when so many physicists read this blog? Pencils out!
I arrived in Tempe, Arizona yesterday for a workshop on “The Nature of the Laws of Physics,” kindly hosted by Paul Davies’ Beyond Center. I’m treating this as a much-needed end-of-semester vacation—with warm desert air, eccentric personalities, talks without theorems, and the sort of meandering philosophical debate I get inexplicably cranky if I haven’t had for a month. Just one problem: I was hoping Cosmic Variance‘s Sean Carroll would arrive to provide much-needed positivist reinforcement against the gangs of metaphysical ruffians, but the California Clarifier backed out—leaving the remaining skeptics to dodge relentless volleys of ill-posed questions only three hours’ drive from the O.K. Corral.
My graduate course 6.896 Quantum Complexity Theory ended last week, with ten amazing student project presentations. Thanks so much to the students, and to my TA Yinmeng Zhang, for making this a great course (at least for me). Almost all of the scribe notes are now available on the course website. But be warned: not only did I not write these notes, not only did I not edit them, for the most part I haven’t read them yet. Use entirely at your own risk.
Want to do graduate study in quantum information at MIT? Yes? Then my colleague Jeff Shapiro asks me to point you to the new website of iQUiSE, our Interdisciplinary Quantum Information Science & Engineering program (motto: “Further Depleting the Supply of Quantum Funding-Related Acronyms Containing the Letters Q and I”). If you’re interested, you apply to a traditional department (such as physics, math, EECS, or mechanical engineering), but specify in your application that you’re interested in iQUiSE. The application deadline is today—but if for some strange reason 17 hours isn’t enough to write your application, there’s always another year.
Dmitry Gavinsky asks me to throw the following piece of meat to the comment-wolves: What exactly should count as a “new” quantum algorithm?
Over at Cosmic Variance, I learned that FQXi (the organization that paid for me to go to Iceland) sponsored an essay contest on “The Nature of Time”, and the submission deadline was last week. Because of deep and fundamental properties of time (at least as perceived by human observers), this means that I will not be able to enter the contest. However, by exploiting the timeless nature of the blogosphere, I can now tell you what I would have written about if I had entered.(Warning: I can’t write this post without actually explaining some standard CS and physics in a semi-coherent fashion. I promise to return soon to your regularly-scheduled programming of inside jokes and unexplained references.)
I’ve often heard it said—including by physicists who presumably know better—that “time is just a fourth dimension,” that it’s no different from the usual three dimensions of space, and indeed that this is a central fact that Einstein proved (or exploited? or clarified?) with relativity. Usually, this assertion comes packaged with the distinct but related assertion that the “passage of time” has been revealed as a psychological illusion: for if it makes no sense to talk about the “flow” of x, y, or z, why talk about the flow of t? Why not just look down (if that’s the right word) on the entire universe as a fixed 4-dimensional crystalline structure?
In this post, I’ll try to tell you why not. My starting point is that, even if we leave out all the woolly metaphysics about our subjective experience of time, and look strictly at the formalism of special and general relativity, we still find that time behaves extremely differently from space. In special relativity, the invariant distance between two points p and q—meaning the real physical distance, the distance measure that doesn’t depend on which coordinate system we happen to be using—is called the interval. If the point p has coordinates (x,y,z,t) (in any observer’s coordinate system), and the point q has coordinates (x’,y’,z’,t’), then the interval between p and q equals
(x-x’)2+(y-y’)2+(z-z’)2-(t-t’)2
where as usual, 1 second of time equals 3×108 meters of space. (Indeed, it’s possible to derive special relativity by starting with this fact as an axiom.)
Now, notice the minus sign in front of (t-t’)2? That minus sign is physics’ way of telling us thattime is different from space—or in Sesame Street terms, “one of these four dimensions is not like the others.” It’s true that special relativity lets you mix together the x,y,z,t coordinates in a way not possible in Newtonian physics, and that this mixing allows for the famous time dilation effect, whereby someone traveling close to the speed of light relative to you is perceived by you as almost frozen in time. But no matter how you choose the t coordinate, there’s still going to be a t coordinate, which will stubbornly behave differently from the other three spacetime coordinates. It’s similar to how my “up” points in nearly the opposite direction from an Australian’s “up”, and yet we both have an “up” that we’d never confuse with the two spatial directions perpendicular to it.
(By contrast, the two directions perpendicular to “up” can and do get confused with each other, and indeed it’s not even obvious which directions we’re talking about: north and west? forward and right? If you were floating in interstellar space, you’d have three perpendicular directions to choose arbitrarily, and only the choice of the fourth time direction would be an “obvious” one for you.)
In general relativity, spacetime is a curved manifold, and thus the interval gets replaced by an integral over a worldline. But the local neighborhood around each point still looks like the (3+1)-dimensional spacetime of special relativity, and therefore has a time dimension which behaves differently from the three space dimensions. Mathematically, this corresponds to the fact that the metric at each point has (-1,+1,+1,+1) signature—in other words, it’s a 4×4 matrix with 3 positive eigenvalues and 1 negative eigenvalue. If space and time were interchangeable, then all four eigenvalues would have the same sign.
But how does that minus sign actually do the work of making time behave differently from space? Well, because of the minus sign, the interval between two points can be either positive or negative (unlike Euclidean distance, which is always nonnegative). If the interval between two points p and q is positive, then p and q are spacelike separated, meaning that there’s no way for a signal emitted at p to reach q or vice versa. If the interval is negative, then p and q are timelike separated, meaning that either a signal from p can reach q, or a signal from q can reach p. If the interval is zero, then p and q are lightlike separated, meaning a signal can get from one point to the other, but only by traveling at the speed of light.
In other words, that minus sign is what ensures spacetime has a causal structure: two events can stand to each other in the relations “before,” “after,” or “neither before nor after” (what in pre-relativistic terms would be called “simultaneous”). We know from general relativity that the causal structure is a complicated dynamical object, itself subject to the laws of physics: it can bend and sag in the presence of matter, and even contract to a point at black hole singularities. But the causal structure still exists—and because of it, one dimension simply cannot be treated on the same footing as the other three.
Put another way, the minus sign in front of the t coordinate reflects what a sufficiently-articulate child might tell you is the main difference between space and time: you can go backward in space, but you can’t go backward in time. Or: you can revisit the city of your birth, but you can’t (literally) revisit the decade of your birth. Or: the Parthenon could be used later to store gunpowder, and the Tower of London can be used today as a tourist attraction, but the years 1700-1750 can’t be similarly repurposed for a new application: they’re over.
Notice that we’re now treating space and time pragmatically, as resources—asking what they’re good for, and whether a given amount of one is more useful than a given amount of the other. In other words, we’re now talking about time and space like theoretical computer scientists. If the difference between time and space shows up in physics through the (-1,+1,+1,+1) signature, the difference shows up in computer science through the famous
P ≠ PSPACE
conjecture. Here P is the class of problems that are solvable by a conventional computer using a “reasonable” amount of time, meaning, a number of steps that increases at most polynomially with the problem size. PSPACE is the class of problems solvable by a conventional computer using a “reasonable” amount of space, meaning a number of memory bits that increases at most polynomially with the problem size. It’s evident that P ⊆ PSPACE—in other words, any problem solvable in polynomial time is also solvable in polynomial space. For it takes at least one time step to access a given memory location—so in polynomial time, you can’t exploit more than polynomial space anyway. It’s also clear that PSPACE ⊆ EXP—that is, any problem solvable in polynomial space is also solvable in exponential time. The reason is that a computer with K bits of memory can only be 2K different configurations before the same configuration recurs, in which case the machine will loop forever. But computer scientists conjecture that PSPACE ⊄ P—that is, polynomial space is more powerful than polynomial time—and have been trying to prove it for about 40 years.
(You might wonder how P vs. PSPACE relates to the even better-known P vs. NP problem. NP, which consists of all problems for which a solution can be verified in polynomial time, sits somewhere between P and PSPACE. So if P≠NP, then certainly P≠PSPACE as well. The converse is not known—but a proof of P≠PSPACE would certainly be seen as a giant step toward proving P≠NP.)
So from my perspective, it’s not surprising that time and space are treated differently in relativity. Whatever else the laws of physics do, presumably they have to differentiate time from space somehow—since otherwise, how could polynomial time be weaker than polynomial space?
But you might wonder: is reusability really the key property of space that isn’t shared by time—or is it merely one of several differences, or a byproduct of some other, more fundamental difference? Can we adduce evidence for the computer scientist’s view of the space/time distinction—the view that sees reusability as central? What could such evidence even consist of? Isn’t it all just a question of definition at best, or metaphysics at worst?
On the contrary, I’ll argue that the computer scientist’s view of the space/time distinction actually leads to something like a prediction, and that this prediction can be checked, not by experiment but mathematically. If reusability really is the key difference, then if we change the laws of physics so as to make time reusable—keeping everything else the same insofar as we can—polynomial time ought to collapse with polynomial space. In other words, the set of computational problems that are efficiently solvable ought to become PSPACE. By contrast, if reusability is not the key difference, then changing the laws of physics in this way might well give some complexity class other than PSPACE.
But what do we even mean by changing the laws of physics so as to “make time reusable”? The first answer that suggests itself is simply to define a “time-traveling Turing machine,” which can move not only left and right on its work tape, but also backwards and forwards in time. If we do this, then we’ve made time into another space dimension by definition, so it’s not at all surprising if we end up being able to solve exactly the PSPACE problems.
But wait: if time is reusable, then “when” does it get reused? Should we think of some “secondary” time parameter that inexorably marches forward, even as the Turing machine scuttles back and forth in the “original” time? But if so, then why can’t the Turing machine also go backwards in the secondary time? Then we could introduce a tertiary time parameter to count out the Turing machine’s movements in the secondary time, and so on forever.
But this is stupid. What the endless proliferation of times is telling us is that we haven’t really made time reusable. Instead, we’ve simply redefined the time dimension to be yet another space dimension, and then snuck in a new time dimension that behaves in the same boring, conventional way as the old time dimension. We then perform the sleight-of-hand of letting an exponential amount of the secondary time elapse, even as we restrict the “original” time to be polynomially bounded. The trivial, uninformative result is then that we can solve PSPACE problems in “polynomial time.”
So is there a better way to treat time as a reusable resource? I believe that there is. We can have a parameter that behaves like time in that it “never changes direction”, but behaves unlike time in that it loops around in a cycle. In other words, we can have a closed timelike curve, or CTC. CTCs give us a dimension that (1) is reusable, but (2) is also recognizably “time” rather than “space.”
Of course, no sooner do we define CTCs than we confront the well-known problem of dead grandfathers. How can we ensure that the events around the CTC are causally consistent, that they don’t result in contradictions? For my money, the best answer to this question was provided by David Deutsch, in his paper “Quantum Mechanics near Closed Time-like Lines” (unfortunately not online). Deutsch observed that, if we allow the state of the universe to be probabilistic or quantum, then we can always tell a consistent story about the events inside a CTC. So for example, the resolution of the grandfather paradox is simply that you’re born with 1/2 probability, and if you’re born you go back in time and kill your grandfather, therefore you’re born with 1/2 probability, etc. Everything’s consistent; there’s no paradox!
More generally, any stochastic matrix S has at least one stationary distribution—that is, a distribution D such that S(D)=D. Likewise, any quantum-mechanical operation Q has at least one stationary state—that is, a mixed state ρ such that Q(ρ)=ρ. So we can consider a model of closed timelike curve computation where we (the users) specify a polynomial-time operation, and then Nature has to find some probabilistic or quantum state ρ which is left invariant by that operation. (There might be more than one such ρ—in which case, being pessimists, we can stipulate that Nature chooses among them adversarially.) We then get to observe ρ, and output an answer based on it.
So what can be done in this computational model? Long story short: in a recent paper with Watrous, we proved that
PCTC = BQPCTC = PSPACE.
Or in English, the set of problems solvable by a polynomial-time CTC computer is exactly PSPACE—and this holds whether the CTC computer is classical or quantum. In other words, CTCs make polynomial time equal to polynomial space as a computational resource. Unlike in the case of “secondary time,” this is not obvious from the definitions, but has to be proved. (Note that to prove PSPACE ⊆ PCTC ⊆ BQPCTC ⊆ EXP is relatively straightforward; the harder part is to show BQPCTC ⊆ PSPACE.)
The bottom line is that, at least in the computational world, making time reusable (even while preserving its “directionality”) really does make it behave like space. To me, that lends some support to the contention that, in our world, the fact that space is reusable and time is not is at the core of what makes them different from each other.
I don’t think I’ve done enough to whip up controversy yet, so let me try harder in the last few paragraphs. A prominent school of thought in quantum gravity regards time as an “emergent phenomenon”: something that should not appear in the fundamental equations of the universe, just like hot and cold, purple and orange, maple and oak don’t appear in the fundamental equations, but only at higher levels of organization. Personally, I’ve long had trouble making sense of this view. One way to explain my difficulty is using computational complexity. If time is “merely” an emergent phenomenon, then is the presumed intractability of PSPACE-complete problems also an emergent phenomenon? Could a quantum theory of gravity—a theory that excluded time as “not fundamental enough”—therefore be exploited to solve PSPACE-complete problems efficiently (whatever “efficiently” would even mean in such a theory)? Or maybe computation is also just an emergent phenomenon, so the question doesn’t even make sense? Then what isn’t an emergent phenomenon?
I don’t have a knockdown argument, but the distinction between space and time has the feel to me of something that needs to be built into the laws of physics at the machine-code level. I’ll even venture a falsifiable prediction: that if and when we find a quantum theory of gravity, that theory will include a fundamental (not emergent) distinction between space and time. In other words, no matter what spacetime turns out to look like at the Planck scale, the notion of causal ordering and the relationships “before” and “after” will be there at the lowest level. And it will be this causal ordering, built into the laws of physics, that finally lets us understand why closed timelike curves don’t exist and PSPACE-complete problems are intractable.
I’ll end with a quote from a June 2008 Scientific American article by Jerzy Jurkiewicz, Renate Loll and Jan Ambjorn, about the “causal dynamical triangulations approach” to quantum gravity.
What could the trouble be? In our search for loopholes and loose ends in the Euclidean approach [to quantum gravity], we finally hit on the crucial idea, the one ingredient absolutely necessary to make the stir fry come out right: the universe must encode what physicists call causality. Causality means that empty spacetime has a structure that allows us to distinguish unambiguously between cause and effect. It is an integral part of the classical theories of special and general relativity.
Euclidean quantum gravity does not build in a notion of causality. The term “Euclidean” indicates that space and time are treated equally. The universes that enter the Euclidean superposition have four spatial directions instead of the usual one of time and three of space. Because Euclidean universes have no distinct notion of time, they have no structure to put events into a specific order; people living in these universes would not have the words “cause” or “effect” in their vocabulary. Hawking and others taking this approach have said that “time is imaginary,” in both a mathematical sense and a colloquial one. Their hope was that causality would emerge as a large-scale property from microscopic quantum fluctuations that individually carry no imprint of a causal structure. But the computer simulations dashed that hope.
Instead of disregarding causality when assembling individual universes and hoping for it to reappear through the collective wisdom of the superposition, we decided to incorporate the causal structure at a much earlier stage. The technical term for our method is causal dynamical triangulations. In it, we first assign each simplex an arrow of time pointing from the past to the future. Then we enforce causal gluing rules: two simplices must be glued together to keep their arrows pointing in the same direction. The simplices must share a notion of time, which unfolds steadily in the direction of these arrows and never stands still or runs backward.
By building in a time dimension that behaves differently from the space dimensions, the authors claim to have solved a problem that’s notoriously plagued computer simulations of quantum gravity models: namely, that of recovering a spacetime that “behave[s] on large distances like a four-dimensional, extended object and not like a crumpled ball or polymer”. Are their results another indication that time might not be an illusion after all? Time (hopefully a polynomial amount of it) will tell.
Follow