NL - iterating all edges of a graph in log space

Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because clique and other similer NP problems belongs to NP and not to NL. Unfortunately, I can't find a satisfying and clear explanation to that fact. Can some one make it more clear for me?

There's absolutely no problem to iterate over all edges in a graph in logspace (even deterministic logspace!). The details depend on how the graph is encoded. For example, if the graph is encoded as an adjacency matrix, then you can simply go over all pairs of vertices.

However, this doesn't give an NL algorithm for clique. The problem is that you need to iterate on $k$-tuples of vertices, for non-constant $k$. This is something you cannot do in logspace.

NP is sometimes described in terms of witnesses. However, the "official" definitions is using nondeterministic Turing machines, which are allowed to have more than one correct move at any given point in time. The class of languages accepted by nondeterministic polytime Turing machines coincides with the class of languages which are given a polynomial size witness and can verify it in polynomial time. Unfortunately, there is no such alternative description for nondeterministic logspace Turing machines.

StackExchange Computer Science Q#109944, answer score: 6