# EX 1: Language theory

## NFA Universality

• Input: a non-deterministic automaton $𝒜$ over the alphabet $Σ$
• Output: $L(𝒜) = Σ^\ast$

$L(𝒜) = Σ^\ast$?

• $∈ PSPACE = coNPSPACE$: Guess $w$ (letter by letter), return “true” iff $w ∉ L(𝒜)$

But it doesn’t work since $𝒜$ is non-deterministic (you could guess a wrong path): so we have to determinize $𝒜$. But as the determinized automaton is exponential in size (wrt to the size of the original one), so we determinize it on the fly: we compute the subset states into which we’re supposed to go step by step, one after the other (each one of them being of polynomial size ⟶ PSPACE).

### PSPACE-hardness

Construct $𝒜$ s.t. (as coPSPACE = PSPACE)

w ∉ L(ℳ) ⟺ Σ^\ast = L(𝒜)

that is:

w ∈ L(ℳ) ⟺ Σ^\ast ≠ L(𝒜)

When is a run of $ℳ$ non-accepting?

• if $q_f ∈ Q \backslash Q_{acc}$
• if a tape extends beyond $p(n)$: $Σ^{p(n)}(Σ\backslash \lbrace # \rbrace)$
• etc…

Bonus: if the automaton is deterministic, it is in $NL$.

## NFA Equivalence

• Input: two non-deterministic automata $𝒜_1, 𝒜_2$ over the alphabet $Σ$
• Output: $L(𝒜_1) = L(𝒜_1)$

### $∈ PSPACE = coNPSPACE$

Guess $w ∈ L(𝒜_1)$ (letter by letter, guess the path), return “true” iff $w ∉ L(𝒜_2)$ (determinization on the fly)

\vert w \vert ≤ 2^{\vert Q_1 \vert + \vert Q_2 \vert}

### PSPACE-hardness

Let $𝒜$ be an automaton.

Let $𝒜_2$ s.t.

L(𝒜_2) = Σ^\ast

To show

L(𝒜) = Σ^\ast ⟺ L(𝒜) = L(𝒜_2)

# EX2: Padding

Show that if $P=PSPACE$, then $EXTIME = EXPSPACE$.

Prove that $EXPSPACE ⊆ EXPTIME$ (the other inclusion is trivial).

Let $L_1$ recognized by $ℳ$ running in expspace ($p(2^n)$):

L_2 = \lbrace (x, 1^{2^{\vert x \vert}}) \mid x ∈ L_1 \rbrace

recognized by $ℳ_2$ running in $p(\vert x \vert + 2^{\vert x\vert})$ space

$L_2 ∈ PSPACE = P$ ⟹ $L_2$ recognized by $ℳ_2’$ running in ptime.

We build $ℳ’$, which takes $x$ and

• compute $2^{\vert x\vert}$ and write $(x, 1^{2^{\vert x \vert}})$: exptime
• simulate $ℳ_2’$: ptime($2^{\vert x \vert}$) = exptime

# EX 5: Closure under morphism

## 1.

Given $L∈NP$, and $f: Σ ⟶ Σ$

f(L) ∈ NP?

Let $ℳ$ recognizing $L$

Build $ℳ’$:

• input: $w$
• guess $a_1, ⋯, a_n$ s.t. $w = f(a_1 ⋯ a_n)$
• execute $ℳ$ on $a_1 ⋯ a_n$

## 2.

Assume that $P$ is closed under morphism.

Let’s prove that $SAT ∈ P$.

With a certificate:

S ≝ \lbrace (φ, \underbrace{u}_{\text{valuation: } \vert u \vert ≤ \vert φ \vert}) \mid u ⊨ φ \rbrace ∈ P

Assume $φ$ and $u$ have disjoint alphabets $Σ$ and $Σ’$.

• $f(Σ) = Σ$
• $f(Σ’) = 0$
SAT = f(S) = \lbrace (φ, 0^{\vert u \vert}) \mid ∃ u; u ⊨ φ \rbrace ≃ \lbrace φ \mid ∃ u; u ⊨ φ \rbrace ∈ P

# EX 6: Unary Languages

Assume

L ≝ \lbrace 1^n \mid ⋯ \rbrace ∈ NP-complete

We have

SAT ≼_{\bf L} L

$φ(t)$ with $t∈ \lbrace 0, 1 \rbrace^\ast$ a partial valuation

SAT(φ, t):
if |t| = |φ|:
if φ(t) has no clauses: YES
else: NO
else:
SAT(φ, t0) ∨ SAT(φ, t1)


On SAT(φ, ε), $2^{\vert φ \vert}$ calls.

But given $φ$, there exists a logspace reduction $R$ s.t.

φ \text{ SAT } ⟺ R(φ) ∈ L

As $L ∈ NP$:

\vert R(φ) \vert ≤ p(\vert φ \vert)

We use $R$ as a hashtable ⟶ $O(p × p_R)$ space used

Tags:

Updated: