A World Without Randomness

By permission of Hector Zenil, artist.

Leonid Levin has originated many great ideas in our field. Indeed he had a share with Stephen Cook in the idea of -completeness as a universality property shared by SAT and several other problems. He also formulated several variations on the measures of the complexity of finite strings that were introduced by Andrey Kolmogorov, Gregory Chaitin, and Ray Solomonoff. This extended to the notion of universal distribution named for Solomonoff and him, by which the prior probability of observing a string is held to be inverse-exponential in the complexity rather than the length of . Levin’s measures take into account the time needed to generate , and have been used to argue that our world may be the output of a universal deterministic program, and hence devoid of ‘true’ randomness.

Today Ken and I want to use Levin’s ideas to talk about what the world would be like if there were no randomness, no coin flipping, not even with slightly biased flips.

Persi Diaconis has famously showed that actual coin flipping by people has bias. The bias is small, but it is non-zero. He has said,

[C]oin tossing is fair to two decimals but not to three. That is, typical flips show biases such as .495 or .503.

This kind of bias, however, still allows one efficiently to extract truly-random bits. We are talking about something more extreme.

Heads

One day when my daughter Jennifer Lipton-O’Oconnor, whom I’ve mentioned for a unique diagonal argument, was quite young, I thought I would talk to her about randomness. I recall we were in our basement area, and I started to explain how quarters, that is American twenty-five cent pieces, could be used to create randomness. She listened a bit and said,

But they always come up heads.

I immediately said no and found a quarter and started to flip it. The first was indeed heads, then the next, and then the next… Finally, after five straight flips in a row of heads, Jen said, “see I told you,” and walked away.

I sat there thinking that this was somehow a failed lesson. I also thought of multiverse ideas. I wondered why I happened to be in the universe where the dad—me—came out looking foolish.

The play “Rosencrantz and Guildenstern are Dead” opens with 157 heads in a row. By multiverse theory there exists a world where that really happened. Playwright Tom Stoppard could have been more subtle and had the coin flips trace out the sequence of prime numbers, in the manner of the novel Contact, or the binary expansion of π. Since the latter are low-complexity deterministic sequences, by Levin’s measures they are scarcely different from all-heads as outcomes. In an unrestricted multiverse, there are worlds where those sequences occur too, for as long as is relevant. Any of those worlds could be our world.

So let’s look at a world of potentially no coins that are random.

SAT Is Not Too Hard

In this world we discover that SAT is relatively easy to solve. Consider our old friends Alice and Bob. Bob’s job is to create an algorithm that generates hard instances of SAT. More formally, Bob is given the input , and each time Alice presses a button, he must create a SAT problem with variables and set of clauses, together with a satisfying assignment . He will give Alice , and her job is to find a satisfying assignment—it need not be , but must satisfy the constraints. Bob’s generator algorithm, let’s denote it by , must run in time polynomial in at each button press. Both Alice and Bob may also increment to at any one step.

The question is: Can Alice solve these generated problems in polynomial time? The answer of course is still open. But Alice can solve them with a budget of slightly more than polynomial time.

Here is how she does it. She uses Levin’s idea. Alice does not look at the clauses directly, but tries to find the generator that Bob used. Each generator is a deterministic Turing machine. It is somewhat unusual in that it keeps outputting instances rather than halting, and can be “kicked” by changing the value of , but we can enumerate them as in a way that any can be loaded and simulated for a given length of time. Bob’s generator is one of the .

Roughly speaking, what Alice does is run them all, in a staggered fashion. The one is run a portion of the time whenever Alice is seeking an answer. Eventually Alice will discover which generator Bob picked. More precisely, she finds the least such that outputs the same formulas as Bob’s generator, and also outputs satisfying assignments for those formulas. The latter need not be the same as Bob’s -es, which Alice never sees.

Deterministic Adaptation

Alice’s algorithm is fixed, and its only variable factor is the interaction with Bob’s . Allowing Bob to increment wards off the triviality of Alice having time to enumerate solutions to all -variable formulas. Since Alice’s algorithm is fixed, and must be capable of simulating any , it cannot be hard-wired to run within any particular polynomial time bound.

It can, however, be coded to abide by any explicitly given constructible time bound that is super-polynomial, however slightly, such as or . Since each is run a constant portion of the time and is super-polynomial, whenever Alice starts including a new in her simulation, she can if-needed eventually “catch up” to where Bob is after some number of button presses, since Bob’s runs in polynomial time. Then she will either discover a mistake made by , and cross it off her list, or will continue forever to give her solutions to the formulas posed by Bob.

When Alice arrives at the correct , her running time to solve formulas posed by Bob also settles down to a multiple of the same polynomial. This is because we can program Alice to push the button for a new formula immediately when she gets a satisfying assignment, without expending steps on other ‘s.

To the outside world, it looks like Alice becomes a smart solver. In reality she is “cheating” by having stumbled upon the right helper to give her cribbed answers. The answers look like they are coming naturally, but they really only exploit Bob’s being a fixed target. Bob is not allowed randomness so as to change the fixed pattern that Alice eventually emulates, nor adaptiveness to Alice’s actions apart from formula requests and incrementing .

Jürgen Schmidhuber, whom Ken just met at the CIG 2013 conference in Niagara Falls, Ontario, has drawn some practical learning aspects of Levin’s universal search. This also underlies his proposal that cosmological processes are pseudorandom. He has itemized several more predictions and possible telltales of a highly deterministic universe. But first let us look at a world that is easier for complexity theorists to imagine, which I (Dick) have said I believe in.

A Similar World

Levin’s original paper with his idea showed that if is true—even if we don’t know a fast algorithm for SAT—then code analogous to Alice becomes a polynomial-time algorithm that gets SAT right on all but finitely many instances. This time a fixed formula of size is given to Alice, rather than formulas from repeated requests to Bob. Alice has the same explicit time budget and staggers time steps among (say ), rejecting unless she sees and verifies a satisfying assignment during her run. If some solves SAT in some polynomial time, then eventually Alice will see its answer at a point where she has spent at most steps on other machines, and once she verifies the answer she stops.

Thus Alice settles down to runtime and eventually gives the right answer on every successive formula. In particular, she eventually starts succeeding on every formula in any stream of instances that are thrown at her.

This gives our sense in which a world without randomness is like a world where . In both cases we know an algorithm that over a long time is observed to become smart at SAT. In one case it’s because of a limitation on the stream of instances, in another it’s because the power to solve SAT in general is really out there, but we observers can’t tell the difference.

The analogy also makes it less farfetched to ask, is our world Bob? Instead of asking metaphysical questions about determinism and mechanism, all we are asking is:

Is it true in our world that every source of SAT instances is eventually 100% solved by ?

Well we can also flip this around to say what this means for the idea of SAT being hard.

What Does This Mean?

Of course most of us believe there are truly-random coin flips, and most believe . Granting these, what does this observation really mean? I think that it says something about how we find hard examples. The standard method for generating hard examples of SAT is to use a source of randomness, and use that to select the instance of SAT.

Thus a solver of SAT, it seems, must inherently be an extractor or randomness. Not, perhaps, in the formal sense of a randomness extractor as we mentioned before, but some kind of extractor nevertheless. The solver must be able to find the solution, which seemingly must contain lots of entropy. I cannot make this precise, but it seems right.

The instance-generation problem has of course been addressed by Levin in numerous papers, in the larger context of distributional complexity. We note especially his 1990 FOCS paper with Russell Impagliazzo, whose title announces that there are “no better ways to generate hard NP instances than picking uniformly at random.” The details require much more attention than we are giving here, since there are even simpler senses in which randomly-generated instances of SAT are almost trivially easy to solve.

Dr. Hector Zenil of Sweden’s Karolinska Institute, who has kindly allowed us to use his low-complexity artwork of Levin above, has written many papers on related subjects. These include a paper on Turing simulation related to lengths of proofs, this essay for the Foundational Questions Institute (FQXi) titled, “The World is Either Algorithmic or Mostly Random,” and an edited book. He also writes a blog on computational life processes, in which these subjects are also covered.

Open Problems

How could one possibly tell one is in a world with no randomness? Well there is almost a way to prove it: flip a coin a million times—perhaps quantumly or noisily—and hit upon a much shorter that generates the output. But the chance of doing this even if it’s true would be infinitesimal. This is why we wonder whether observing success at SAT against instance generators is more plausible, along with Schmidhuber’s other telltales.

Short of being in it, what more can we say about a world with no randomness?

[changed Levin pic and added material from Hector Zenil]