What if there were no coin flips?

Leonid Levin has originated many great ideas in our field. Indeed he had a share with Stephen Cook in the idea of ${\mathsf{NP}}$-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 ${x}$ is held to be inverse-exponential in the complexity rather than the length of ${x}$. Levin’s measures take into account the time needed to generate ${x}$, 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.

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 ${1^{n}}$, and each time Alice presses a button, he must create a SAT problem with ${n}$ variables and set ${C}$ of ${O(n)}$ clauses, together with a satisfying assignment ${x}$. He will give Alice ${C}$, and her job is to find a satisfying assignment—it need not be ${x}$, but must satisfy the constraints. Bob’s generator algorithm, let’s denote it by ${G}$, must run in time polynomial in ${n}$ at each button press. Both Alice and Bob may also increment ${n}$ to ${n+1}$ 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 ${C}$ 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 ${(C,x)}$ rather than halting, and can be “kicked” by changing the value of ${n}$, but we can enumerate them as ${G_1,G_2,G_3,\dots}$ in a way that any ${G_i}$ can be loaded and simulated for a given length of time. Bob’s generator is one of the ${G_i}$.

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

Alice’s algorithm is fixed, and its only variable factor is the interaction with Bob’s ${G}$. Allowing Bob to increment ${n}$ wards off the triviality of Alice having time to enumerate solutions to all ${n}$-variable formulas. Since Alice’s algorithm is fixed, and must be capable of simulating any ${G_i}$, 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 ${t(n)}$ that is super-polynomial, however slightly, such as ${n^{\log n}}$ or ${n^{\log\log n}}$. Since each ${G_i}$ is run a constant portion of the time and ${t(n)}$ is super-polynomial, whenever Alice starts including a new ${G_i}$ in her simulation, she can if-needed eventually “catch up” to where Bob is after some number ${s}$ of button presses, since Bob’s ${G_j}$ runs in polynomial time. Then she will either discover a mistake made by ${G_i}$, and cross it off her list, or ${G_i}$ will continue forever to give her solutions to the formulas posed by Bob.

When Alice arrives at the correct ${G_j}$, 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 ${t(n)}$ steps on other ${G_i}$‘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 ${n}$.

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 ${\mathsf{P = NP}}$ 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 ${C}$ of size ${n}$ is given to Alice, rather than formulas from repeated requests to Bob. Alice has the same explicit time budget ${t(n)}$ and staggers time steps among ${G_1,\dots,G_r}$ (say ${r = \log_2 t(n)}$), rejecting unless she sees and verifies a satisfying assignment during her run. If some ${G_j}$ solves SAT in some polynomial ${q(n)}$ time, then eventually Alice will see its answer at a point where she has spent at most ${2^j q(n)}$ steps on other machines, and once she verifies the answer she stops.

Thus Alice settles down to ${O(q(n))}$ 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 ${\mathsf{P = NP}}$. In both cases we know an algorithm ${\cal A}$ 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.

Is it true in our world that every source of SAT instances is eventually 100% solved by ${\cal A}$?

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 ${\mathsf{P \neq NP}}$. 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 ${x}$ 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]

1. August 23, 2013 1:12 pm

As Leibniz observed, <i<Randomness is Relative to POV.

2. August 23, 2013 1:28 pm

If you live in a world without a normal source of randomness, how many truly random bits do you need to simulate a world like ours for 20 billion years so that the possibility of detecting the lack of randomness from the inside is 10^-100? Wouldn’t a few thousand random bits be enough, assuming standard cryptographic conjectures?

3. August 23, 2013 4:42 pm

If P=NP then comedic possibilities become near-certainties…

4. August 23, 2013 5:11 pm

Einstein was right: the world isn’t random in the least. But he refused to admit what seems obvious now – that it will forever look random to us living beings… because we’re part of it!

5. August 23, 2013 5:22 pm

There are concepts that we have invented for ourselves that appear to be pure abstractions, that do not manifest themselves in our universe. To me ‘random’ seems to be one of those. Another is ‘perfect’, and I still have deep suspicions about ‘infinite’. But I certainly agree that my own POV is in itself neither universal nor objective.

In some ways a world with no randomness — essentially a fully deterministic world — is a lot less interesting than a world full of magic. But it still can be chaotic enough that our species could reach the end of time without fully understanding even a fraction of it, and given the limitations of our species, even if we iterated everything no single person would ever be able to keep it all in there head at anytime. That still leaves plenty of room to keep things interesting…

Paul.

6. August 23, 2013 5:58 pm

Okay, no one else is doing the calculation, so I should. The universe so far could have performed about 10^120 operations (http://arxiv.org/abs/quant-ph/0110141). Say we want to simulate a universe for much longer that than, say out to 10^200 operations, using a strong n-bit cryptographic hash function in counter mode as a pseudorandom number generator. If the simulated universe folk know the generator but not the key, they need around sqrt(2^n) operations to detect nonrandomness. Thus, we need n = log_2 10^400 = 1329 bits. So a deterministic universe is fewer than 2000 bits away from a random universe.

7. August 26, 2013 10:10 am

Another idea worth recalling here is Peirce’s notion that the balance of randomness versus ruliness in the universe as a whole might change over time, perhaps even exhibiting growing lawfulness as time goes on, as I mentioned in an earlier discussion.

This rather echoes the Epicurean/Lucretian concept of the Clinamen, or “Swerve”.

8. August 29, 2013 9:40 pm

So if there is no randomness then P=NP or is close. But if P=NP that doesn’t mean there can’t also be randomness, did I get that right?

9. 