Theorem: space and time with does not suffice to sort a list.
Simpler theorem:
space and time does not suffice to output “which of the numbers between and appear exactly once in my list”.
Exercise: Why does the simpler theorem basically imply the main theorem?
Pf of simpler theorem:
We can think of a list sorting algorithm as a “branching program”
Each state is a configuration that your memory could be in. At each time step, you’re at some memory state and then you read an input bit and transition to one of two memory states on the next time step.
We say that a vertex in the branching program is good for list if:
Starting from and running the branching program on for steps (i.e., following the arrows that dictates) results in outputting at least distinct unique values in , and no non-unique values.
Define to be the following distribution over lists:
Each element of is a random element of .
Lemma:
Fix vertex . is good.
Proof:
You’re only looking at of the list, so you really have no basis for any of your guesses that elements are unique. Each time you guess that an element is unique, there’s at least a 1% chance (probably really like 30%) that you’re wrong, and these are all independent.
Split the branching program into length chunks. Let be the vertices at the first time slice of each chunk.
Lemma: For most , all vertices in are bad.
Proof: contains vertices. Each vertex is good with probability at most . So the chance that any vertex in is good is at most , which is tiny (for large , which is what I care about).
Lemma:
Fix a list with at least unique elements. Suppose that all vertices in are bad for .
Then, the branching program doesn’t correctly output the unique elements of .
Proof: If all vertices in are bad, then we output at most values. This isn’t enough.
Lemma: Most have at least unique elements.
Conclusion:
Combining all the Lemmas, we find that most have a bunch of unique elements, but the branching program doesn’t output them all. That is, the branching program usually outputs the wrong answer. So, we didn’t have enough space / time.
