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)$

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: