Exercises 3: Space hierarchy theorem

EX 1: Space hierarchy theorem

If $f, g$ are space-constructible, and $f = o(g(n))$, then

\[SPACE(f(n)) ⊊ SPACE(g(n))\]

Find

\[L ∈ SPACE(g(n)) \backslash SPACE(f(n))\]

Let

\[L ≝ \lbrace (ℳ, w) \mid ℳ \text{ rejects } (ℳ, w) \text{ in space } ≤ g(\vert (ℳ, w) \vert)\rbrace ∈ SPACE(g(n))\]

(because we have a SPACE-OUT)

Assume $ℳ ∈ SPACE(f(n))$ (by abuse of notation) recognizes $L$.

On $(ℳ, w)$, $ℳ$ takes $SPACE(f((ℳ,w)))$, so for $w$ long enough: $f((ℳ, w)) ≤ g((ℳ, w))$.

• If $(ℳ, w) ∈ L$, $ℳ$ accepts $(ℳ, w)$ ($ℳ$ recognizes $L$), therefore $ℳ$ rejects $(ℳ, w)$ (definition of $L$)
• and conversely

EX 2: Polylogarithmic space

Using the space hierarchy theorem:

\[∀k, SPACE(\log^k) ⊊ PSPACE(\log^{k+1})\]

Horn-SAT is P-complete so if $polyL = P$: Horn-SAT ∈ P, so that there exists $k$ s.t.

\[Horn\text{-}SAT ∈ SPACE(\log^k)\]

Hardness: $∀L∈ polyL$, $L$ can be solved using $SPACE(\log^k)$: contradiction.

NB: complete problems cheracterize nicely their complexity classes

EX 3: Padding argument

1.

Assume that there exists $c>0$ s.t.:

\[SPACE(n^c) ⊆ NP\]

Let’s show that

\[PSPACE ⊆ NP\]

that is:

\[∀k > c, \; SPACE(n^k) ⊆ NP\]

Let $L ∈ SPACE(n^k)$: $ℳ$ solves $L$ in space $n^k$

\[\tilde{L} ≝ \lbrace (x, 1^{\vert x \vert^{k/c}}) \mid x ∈ L\rbrace\]

so that $ℳ$ solves $\tilde{L}$ in space

\[\vert x \vert^k ≤ \vert (x, 1^{\vert x \vert^{k/c}}) \vert^c\]

Therefore:

\[\tilde{L} ∈ SPACE(n^c) ⊆ NP\]

and thus:

\[L ∈ NP\]

(erase the $1$’s at the end)

2.

Assume $SPACE(n^c) = NP$, so $SPACE(n^c) ⊆ NP$

Then by question 1: $PSPACE ⊆ NP$

And as $NP ⊆ PSPACE$:

\[PSPACE = NP = SPACE(n^c)\]

impossible, because of the space hierarchy theorem: the tower of $n^k, k≥0$ cannot collapse into one $n^c$.

EX 4: PSPACE-complete problem

Problem $𝒫$

• input: a TM $ℳ$, a word $w$, a number $t$ in unary
• output: does $ℳ$ accept $w$ within space $t$?

1. $𝒫 ∈ PSPACE$: just execute $ℳ$ on $w$: as $t$ is in the input ($\vert t \vert ≤ n$), the space used is polynomial

2. $𝒫$ is PSPACE-complete: given $ℳ$ in $PSPACE$ as an input (but you don’t know for which polynomial $P$), you try all the $P ≝ n ⟼ n^k$ until it fits the execution of the machine, and then set $t = P(\vert w \vert)$

EX 5: PSPACE and games

1.

By Savitch and Immermann theorems: $PSPACE = NPSPACE = coNPSPACE$.

To be sure to win = to have a winning strategy

Player 1 wins at node $n$ iff for any children of $n$: $n’$, player loses at $n’$.

So there is a recursive algorithm: in exptime, but the size of the stack is polynomial ⟶ in PSPACE.

2.

• Existential quantifier: player 1
• Universal quantifier: player 2