HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthetrianglehashowlogspace

Problem

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.

Solution

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}$.

Code Snippets

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

Context

StackExchange Computer Science Q#114885, answer score: 19

Revisions (0)

No revisions yet.