Bsrgvty

How to get the sum, difference, product, and quotient from a macro in ConTeXt or plain TeX?

How does "unlimited holidays" work in practice?

What's a good use case for SELECT * in production code?

Advance of d4 in the Ruy Lopez

My professor changed a take-home test to an in-class test with no notice. Can I fight the grade?

If password expiration is applied, should door-lock expiration be applied too?

How do I solve this equation with Mathematica?

I can't understand how probability makes sense

Select polygons with 5 or more points

Why 401k contribution as % of salary vs. fixed amount per pay check?

Bought a book that is in the public domain ... but the T&A of company says I can't redistribute it

I peer reviewed a paper and found it to be sound - technically and language-wise. How should I write the review report?

Why is tan short for tangent?

How can I offer my prayers for an atheist?

Do one quarter of Swedes named 'Ali' have a criminal record?

What does "Massage with salt" mean in a recipe?

My advisor wants me to make my PhD thesis weaker

How can I pass a collection of exceptions as a root cause?

Why is it runway "1" instead of "01" in America?

Barring Epic Boons, is there a way to gain immunity to fire damage?

How often are there lunar eclipses on Jupiter

Why are the norm symbols || not aligned in this situation?

Combining two plots with separate frame tick styles

Why would Earth be long-term unsuitable for an advanced alien species that's already colonized it?

How is the problem, G has no triangle in Logspace?

Logspace TransducerWhy is it necessary to use binary numbers in logspace?Reachibility between first and last layer in grid graph in logspaceIs the power of a natural number logspace-computable?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

5

1

$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 $binomn3$ 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⟩ : $. 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.

graphs turing-machines space-complexity

share|cite|improve this question

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

$endgroup$

add a comment
 | 

5

1

$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 $binomn3$ 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⟩ : $. 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.

graphs turing-machines space-complexity

share|cite|improve this question

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

$endgroup$

add a comment
 | 

$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 $binomn3$ 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⟩ : $. 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.

graphs turing-machines space-complexity

share|cite|improve this question

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

$endgroup$

share|cite|improve this question

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

share|cite|improve this question

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

edited Sep 20 at 5:40

Nayuki

58833 silver badges1111 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

asked Sep 18 at 9:04

Shirley SamShirley Sam

8566 bronze badges

2 Answers
2

active

oldest

votes

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.

share|cite|improve this answer

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So we need to choose a 3-tuple non deterministically right?
  $endgroup$
  – Shirley Sam
  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$
  – Shirley Sam
  Sep 18 at 10:39
  

  
  
  
  

add a comment
 | 

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 textttn)$ bits to store an integer between $1$ and $textttn$.

share|cite|improve this answer

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

$endgroup$

add a comment
 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f114885%2fhow-is-the-problem-g-g-has-no-triangle-in-logspace%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

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.

share|cite|improve this answer

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So we need to choose a 3-tuple non deterministically right?
  $endgroup$
  – Shirley Sam
  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$
  – Shirley Sam
  Sep 18 at 10:39
  

  
  
  
  

add a comment
 | 

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.

share|cite|improve this answer

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So we need to choose a 3-tuple non deterministically right?
  $endgroup$
  – Shirley Sam
  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$
  – Shirley Sam
  Sep 18 at 10:39
  

  
  
  
  

add a comment
 | 

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

share|cite|improve this answer

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

$endgroup$

share|cite|improve this answer

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

answered Sep 18 at 9:30

StevenSteven

2,51988 silver badges1515 bronze badges

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 textttn)$ bits to store an integer between $1$ and $textttn$.

share|cite|improve this answer

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

$endgroup$

add a comment
 | 

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 textttn)$ bits to store an integer between $1$ and $textttn$.

share|cite|improve this answer

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

$endgroup$

add a comment
 | 

$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 textttn)$ bits to store an integer between $1$ and $textttn$.

share|cite|improve this answer

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

$endgroup$

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

share|cite|improve this answer

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges

answered Sep 18 at 11:26

David RicherbyDavid Richerby

75.9k1717 gold badges117117 silver badges208208 bronze badges