# How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-tuples in the tape, then how come my solution is limited to log-space?

As far as my understanding, listing all the 3-tuples in the tape would need $$\binom{n}{3}$$ combinations, and hence, $$O(n^3)$$ space.

I am not able to find the flaw in my understanding, grateful ever for the hint.

P.S. This reference is from our course slide:

Let $$L$$ be the language $$\{⟨G⟩ \: | \: G\text{ has no triangle}\}$$. Then $$L$$ can be recognized in log-space as follows: On the work tape, the machine $$M$$ can write all 3-tuples of the vertices of $$G$$. For each tuple written, the machine checks if there is a triangle passing through those vertices. If all tests fail, then $$M$$ accepts, otherwise $$M$$ rejects. The space used by $$M$$ is enough to store three vertex identifiers, therefore $$L$$ is in log-space.

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle.

You can just enumerate the 3-tuples one at a time and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.

• So we need to choose a 3-tuple non deterministically right? – Shirley Sam Sep 18 '19 at 9:31
• There is no need to use nondeterminism. Let $n$ be the number of vertices of $G$ and suppose that they are indexed from $0$. A 3-tuple is just 3 integers $a,b,c$. Initially $a=b=c=0$. To generate the next 3-tuple simply increment $c$ by one, if it is equal to $n$ set it to 0 and increment $b$ by one. If $b$ is equal to $n$, set it to 0 and increment $a$ by one. If $a$ is equal to $n$ you are done enumerating all 3-tuples. For each tuple that you generate in this way, check whether it induces a triangle. If so, reject. If it doesn't, move to the next tuple. If you reach the end, accept. – Steven Sep 18 '19 at 9:42
• Thankyou, I got it!! – Shirley Sam Sep 18 '19 at 10:39
FOR x := 1 TO n DO
FOR y := 1 TO n DO
FOR z := 1 TO n DO
IF E(x,y) && E(y,z) && E(z,x) THEN REJECT
ACCEPT


Each of the variables x, y and z requires $$\Theta(\log \texttt{n})$$ bits to store an integer between $$1$$ and $$\texttt{n}$$.