Exercises 4: PSPACE-complete problems, Padding

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

Leave a comment