\begin{equation} \text{STCONN} = \qty {\langle G, S, t \rangle : \text{$\exists^{?}$ a path from s $\to$ t $\in$ G}} \end{equation}

we solve this with BFS or DFS; but those algorithms’ working sets require linear space. Turns out, we can solve this algorithm \(\text{STCONN} \in \text{SPACE}\qty(\log^{2}\qty(n))\)

• for directed \(G\), we are not sure if its in L.
• for undirected \(G\), Omer showed that its in L

open problem: Savitch’s Algorithm is really really slow; we are not sure if there is an algorithm in which we can solve it in better time.

To put some math behind that very, extremely simple Dyson’s Model, we will declare a vector space \(K\) which encodes the possible set of states that our “cell” can be in. Now, declare a transition matrix \(M \in \mathcal{L}(K)\) which maps from one state to another.

Finally, then, we can define a function \(P(k)\) for the \(k\) th state of our cell.

That is, then:

\begin{equation} P(k+1) = M P(k) \end{equation}

(as the “next” state is simply \(M\) applied onto the previous state).

This is a theory that come back to CAPM.

the stock indicies