5
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So we need to choose a 3-tuple non deterministically right? $\endgroup$ – Manika Sharma Sep 18 at 9:31
  • 5
    $\begingroup$ 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. $\endgroup$ – Steven Sep 18 at 9:42
  • 1
    $\begingroup$ Thankyou, I got it!! $\endgroup$ – Manika Sharma Sep 18 at 10:39
19
$\begingroup$
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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.