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

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

Tags:

Updated: