STCON in L using matrix multipication algorithm?

Question

I'm trying to understand why the following is incorrect.

Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-loop (filling the main diagonal with $1$'s) we can multiple this matrix with itself n times, each time checking if the $s,t$ entry is $1$, and if so returning true.

We know multiplying binary matrices is in $L$ (need to "save" only couple of indices), and by also saving $n$ (number of total matrix multiplications) one can solve $STCON$ also in $L$.

Where am I wrong here?

Answer 1

A machine runs in logarithmic space if the working space it requires (excluding the read-only input and the write-only output) is at most logarithmic in the number of bits required to represent the input.

For matrix multiplication, the input is the two matrices, and the output is their product. The only working space is, as you say, the "loop counters" for stepping through the current row and column to compute the next bit of the output.

For graph connectivity, the input is the adjacency matrix of the graph, along with the two vertices of interest, and the output is the single bit "yes" or "no". Your proposed algorithm requires remembering the matrix of paths you've discovered so far, which has size $n^2$, and that's not logarithmic.

Answer 2

L contains decision problems. The output of a decision problem is a single bit (not an entire matrix). Contrary to what you wrote, matrix multiplication is not a decision problem so it is not in L. I suggest you check the definition of L and the definition of STCON (which is a decision problem), then try applying your argument with this in mind. Try to write out your algorithm for STCON explicitly and see how much space it uses. You'll find yourself trying to keep a copy of an entire matrix in memory; but that takes more than logarithmic space.