# 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

## 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

Tags:

Updated: