Exercises 2 : SPACE and NL (2)

EX 1 : Warm up

1.

$𝒫$ = Deciding if a non-deterministic automaton $𝒜$ accepts a word $w$

  1. $𝒫 ∈ NL$ : guess the sequence of transitions to take, and update a pointer indicating on which current state we are (when reading the transitions).

  2. $REACH ≼ 𝒫$: you turn the directed graph into a non-deterministic automaton (by labelling all the edges by $ε$), $s$ being the initial state, $t$ is a final state. Then, just check that $ε$ is accepted.

\[G ≝ (E, V), s, t \leadsto 𝒜 ≝ (Q ≝ V, Δ ≝ \lbrace (x, y, ε) \mid (x,y)∈E \rbrace, I = \lbrace s \rbrace, F ≝ \lbrace t \rbrace)\] \[REACH(G,s,t) ⟺ w ∈ L(𝒜)\]

2.

$𝒫$ : deciding if a directed graph is strongly connected

  1. $𝒫 ∈ NL$ :
  • M1: you loop through all the possible pairs (with 2 counters) of vertices and check with REACH is they are connected.
  • M2: by resorting to the fact that $coNL = NL$: guess $x$ and $x’$, and check if they are not connected
  1. $REACH ≼ 𝒫$: given $(G, s, t)$, let’s build a $G’$ s.t.:
\[G' \text{ is strongly connected } ⟺ s, t \text{ are connected } in G\]

Let $G’ ≝ G$, and we add, for all $i ∈ V$, the edges $(i, s)$ and $(t, i)$

  • $⟹$ : is easy
  • $⟸$ : we have a path from $s \overset{π}{⟶} t$. Then for all $(i, i’) ∈ V^2$, \(i ⟶ s \overset{π}{⟶} t ⟶ i'\) so $i$ and $i’$ are connected in $G’$

3.

$𝒫$ : deciding if a directed graph has a cycle

  1. $𝒫 ∈ NL$ : guess a node $x$, and $REACH(G, x, x)$ ?

  2. $REACH ≼ 𝒫$: given $(G, s, t)$, let’s build an acyclic $G’$ s.t.:

\[REACH(G, s, t) ⟺ Reach(G', s', t') ⟺ Cycle(G'') \text{ where } G'' = G + (t', s')\]

$G’$ is made of $n$ copies of $G$ ($n = \vert V \vert$) s.t.

  • $∀(i, j) ∈ V$, for each $i$ of every level, there is an edge between $i$ and $j$ of next level
  • $∀i ∈ V$, for each $i$ of every level, there is an edge between $i$ and $i$ of next level

EX 2 : Restrictions of the SAT problem

1.

Assumption: SAT is NP-complete for logspace reduction.

  1. 3-SAT ∈ NP ?

  2. Given $S$ a SAT formula

Let’s consider $L_1 ∨ L_2 ∨ C$ a clause of $S$, where $C$ non trivial

  • $(L_1 ∨ L_2 ∨ C) \leadsto (L_1 ∨ L_2 ∨ \underbrace{x}_{\text{fresh variables}}) ∧ (¬x ∨ C)$
  • Iterate on $¬x ∨ C$

TM:

  • Input: $L_1 ∨ L_2 ∨ C ∧ ⋯$ where the literals are encoded in binary

  1. On a tape $B$ ⟶ count the variables $N$, store $(N+1)$ on $B$

  2. Start reading the input:

(1) copy L_1 to the output
copy L_2 to the output

if C = L_3
  copy it to the ouput
else
  copy B to the output
  write ∧ ¬B ∨
  increment B
  goto (1)

or, to have the pointer only moving forward:

(1) copy L_1 to the output
(2) copy L_2 to the output

copy (fst C) to the B_3
if (fst C = C)
  write B_1 ∨ B_2 ∨ B_3
else
  write (B_1 ∨ B_2 ∨ x) ∧ ¬x ∨
  copy B_3 to B_1, goto (2)

2.

The clause $x_i ∨ x_j$ is seen as $¬ x_i ⟹ x_j$

We build a graph in which $¬x_i ⟶ x_j$.

If there exists a cycle, then the formula is not satisfiable.

for all x, ¬x:
  reach(G, x, ¬x)
  reach(G, ¬x, x)

if true ⟹ unsat

By induction on $1 ≤ i ≤n$, we build $G_i’s$ s.t.

  • $G_0 = G$
  • for $i ∈ ⟦1, n⟧$, assume $G_{i-1}$ is constructed

    • if there is a path from $¬x_i$ to $x_i$ in $G_{i-1}$:

      • set $x_i$ to true, $G_i = G_{i-1}$

    • else:

      • set $x_i$ to false, $G_i = G_{i-1} + (x_i ⟶ ¬ x_i)$

⟹ $G_n$ does not have a path $x_i ⟶ ¬ x_i ⟶ x_i$ ?

By induction on $i$:

  • for $G_0$, it’s true by hypothesis
  • for $1≤i≤n$ : assume it’s true for $G_{i-1}$
    • case 1: if $G_i = G_{i-1}$: it’s true
    • case 2: $G_i = G_{i-1} + (x_i ⟶ ¬ x_i)$ but there’s no path from $¬ x_i$ to $x_i$ in $G_{i-1}$ by hypothesis, so we’re done.

Is $(x_1, \ldots, x_n)$ a valuation of $S$ ?

Let’s show that $(x_1, \ldots, x_n)$ is not a valuation of $S$ iff there exists an implication in $S$ which is false

For an edge $(¬ x_i, x_j)$ in $G$, the implication is false iff $x_i = true$ and $x_j = false$

Let’s assume that $x_i$ is true and $x_j$ is false.

  • As $x_i$ is true, $x_j$ is false:

    • there exists a path $¬x_i \overset{π}{⟶} x_i$ in $G_n$
    • we also have $x_j ⟶ ¬ x_j$

Leave a comment