Exercises 1 : SPACE and NL

EX 1: Graph representation and why it doesn’t matter

1.

To write $m_{i,j}$, the machine goes to the $i$-th bullet (with a counter 1) and look for $j$ in the list. If $j$ is found, $m_{i,j} = 1$, else $m_{i,j} = 0$

There are also two other counters: one of rows, and one of columns.

n = number of ∙ on the input tape
pointer = 0
for i in range(n):
  for counter in range(n):
    if counter == pointer:
      write 1
      pointer+=1
    else:
      write 0
  move pointer after ∙

2.

To write the list of the neighbors of the vertex $i$, the machine look for all the $m_{i, k}$ or $m_{k, i}$ for $0 ≤ k ≤ n-1$ that are equal to $1$ (with a counter up to $n^2$).

The space used is $\log n^2 = 2 \log n$, which can be done in $\log n$ by the speedup theorem.

EX 2 : Inclusion of complexity classes

If there exists a deterministic TM that computes $f(\vert x \vert)$ in $O(f(\vert x \vert))$ space given $x$ as input, show that:

\[NSPACE(f(n)) ⊆ DTIME(2^{O(f(n))})\]

Let $M$ running in space $f(n)$ with $k$ tapes, states $Q$, alphabet $Γ$.

With $n = \vert x \vert$, the number of configurations of $M$ is:

\[\vert Q \vert^k \vert Γ \vert^{k β f(n)} = 2^{O(f(n))}\]

since a configuration is given by:

  • the tape $α_1 ⋯ α_{β f(n)}$
  • the state $q$
  • and that, for the $k$ tapes

The function has to be space constructible, to ensure that we can read the input, so that $n = O(f(n))$

The question “does $M$ accept $x$?” is tantamount to finding a path in graph of configurations from the initial configuration to an accepting configuration.

Any reasonable polynomial algorithm (like BFS), because

\[P(\vert V \vert + \vert E \vert) = P((2^{O(f(n))})^2) = 2^{O(f(n))}\]

for any polynomial $P$

EX 3 : Restrictions in the definition of $SPACE(f(n))$ don’t matter

1.

Show that \(SPACE'(f(n)) ⊆ SPACE(f(n))\)

If there exists a TM $M$ running in space bounded by $f(n)$ s.t. $M$ accepts $x$ iff $x ∈ L$. If $x∉L$, $M$ may not terminate.

We implement a timeout:

$M ∈ SPACE’(f(n))$:

  • if $x$ is accepted by $M$, it is necessary that it can be done in some $a^{f(n)}$ where $a$ is a constant depending on $M$

We build $M_0$ out of $M$ by:

  • running $M$

  • while at the same time keeping a counter $c$ up to date, incremented by 1 at each step

  • ⟶ if $c > a^{f(n)}$, $M_0$ rejects, else $M_0$ behave like $M$

$x$ is accepted by $M$ iff $x$ is accepted by $M_0$

2.

For the time, we proceed as we did previously, but ofr the space, we just put a marker to denote the end of the allowed space on each tape.

EX 4: The Dick’s Language

1.

We have a counter, which is:

  • incremented whenever we read (
  • decremented whenever we read )

we accept iff the counter equals 0 at the end.

2.

For any finite number of parenthesis:

  1. we first run the previous algorithm, by not distinguishing the different types of parenthesis

  2. then, we check one by one for each opening parenthesis that the corresponding closing parenthesis (when the counter hits 0) is of the right type.

We only have counters and one parenthesis type checking procedure (in constant space) ⟶ logarithmic space.

EX 5: NL alternative definition

1.

$NL$:

non-deterministic TM in logspace

$NL_{certif}$:

Deterministic TM in logspace accepting iff there exists a polynomial $p$ s.t. and a TM $M$ with a certificate tape (extra read-only input tape that can be read once at most): \(x∈L ⟺ ∃ u, \vert u \vert ≤ p(\vert x \vert) \text{ and } M \text{ accepts } (x, u)\)

$NL_{certif} ⊆ NL$:

Let $A ∈ NL_{certif}$, we construct $M_0$:

  • runs $A$
  • if $A$ wants to read some bit of $u$, just guess it. You won’t ever need it later anyway, since the certificate tape is read once.

$NL ⊆ NL_{certif}$:

Let $M∈ NL$, we construct $M_0$, which given the certificate

  • $y ∈ \lbrace 0, 1 \rbrace^\ast$, the path taken by $M$ from the initial configuration to the end one, with $\vert y \vert ≤ p(\vert x \vert)$

does

  • $M_0$ runs $M(x)$ along $y$

Since

\[NPSPACE(f(n)) ⊆ DTIME(2^{O(f(n))})\]

it follows that:

\[NPSPACE(\log(n)) ⊆ PTIME(n)\]

2.

If which remove the read-once constraint:

\[NL_{certif} = NP\]

To show that $NP ⊆ NL_{certif}$, it suffices to show that the NP-complete (so that every reduction made is in Logspace (reduction made in the Cook-Levin theorem)) problem 3-SAT is in $NL_{certif}$, which is the case.

Leave a comment