Space Hierarchy Theorem - Proof

Proof

The goal here is to define a language that can be decided in space but not space . Here we define the language :

L = \{~ (\langle M \rangle, 10^k): M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) ~ \}

Now, for any machine that decides a language in space, will differ in at least one spot from the language of, namely at the value of . The algorithm for deciding the language is as follows:

  1. On an input, compute using space-constructibility, and mark off cells of tape. Whenever an attempt is made to use more than cells, reject.
  2. If is not of the form for some TM, reject.
  3. Simulate on input for at most steps (using space). If the simulation tries to use more than space or more than operations, then reject.
  4. If accepted during this simulation, then reject; otherwise, accept.

Note on step 3: Execution is limited to steps in order to avoid the case where does not halt on the input . That is, the case where consumes space of only as required, but runs for infinite time.

The above proof holds for the case of PSPACE whereas we must make some change for the case of NPSPACE. The crucial point is that while on a deterministic TM we may easily invert acceptance and rejection (crucial for step 4), this is not possible on a non-deterministic machine.
For the case of NPSPACE we will first modify step 4 to:

  1. If accepted during this simulation, then accept; otherwise, reject.

We will now prove by contradiction that can not be decided by a TM using cells.
Assuming can be decided by a TM using cells, and following from the Immerman–Szelepcsényi theorem follows that can also be determined by a TM (which we will call ) using cells.
Here lies the contradiction, therefor our assumption must be false:

  1. If (for some large enough k) is in then will accept it, therefor rejects, therefor is not in (contradiction).
  2. If (for some large enough k) is not in then will reject it, therefor accepts, therefor is in (contradiction).

Read more about this topic:  Space Hierarchy Theorem

Famous quotes containing the word proof:

    “The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
    —Lenny Bruce (1925–1966)

    “War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
    —M.F.K. Fisher (1908–1992)

    “Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
    —Henry David Thoreau (1817–1862)