Otdfbt

Oil draining out shortly after turbo hose detached/broke

How much web presence should I have?

Playing a trill with grace note ending

When to use и or а as “and”?

Why vspace-lineskip removes space after tikz picture although it stands before the picture?

DateTime.addMonths skips a month (from feb to mar)

Should I list a completely different profession in my technical resume?

Parsing text written the millitext font

How to represent jealousy in a cute way?

Dedicated bike GPS computer over smartphone

Does it make sense to use a wavelet that is equal to a sine of one period?

Was planting UN flag on Moon ever discussed?

How to generate list of *all* available commands and functions?

Why does there seem to be an extreme lack of public trashcans in Taiwan?

That's not my X, its Y is too Z

How can powerful telekinesis avoid violating Newton's 3rd Law?

How do I avoid typing "git" at the begining of every Git command?

Do Veracrypt encrypted volumes have any kind of brute force protection?

Are the guests in Westworld forbidden to tell the hosts that they are robots?

What exactly "triggers an additional time" in the interaction between Afterlife and Teysa Karlov?

How can I list the different hex characters between two files?

If the pressure inside and outside a balloon balance, then why does air leave when it pops?

How do I type a hyphen in iOS 12?

C++ logging library

NL - iterating all edges of a graph in log space

Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1Show that k-clique lies in LP, NP and specialised Turing MachinesLooking for an example of proving space upper bounds for computing functions on a DTMCovering a graph with non-overlapping cliquesHow to use succinct circuits to construct an EXPTIME complete problem?Why L is defined as L = SPACE$( log n)$ instead of L = SPACE$(log^2 n)$ or L = SPACE$(sqrt n)$?Meaning of $NL$ Complexity ClassThere are parsimonious reductions between all NP-Complete problems: Well-known conjecture?Constructing a DFA $M$ such that $L(M) = L(A) bigtriangleup L(B)$ with a kind of log-space TM

4

$begingroup$

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?

complexity-theory graph-theory

share|cite|improve this question

asked May 27 at 19:39

LioHLioH

805

$endgroup$

add a comment | 

4

$begingroup$

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?

complexity-theory graph-theory

share|cite|improve this question

asked May 27 at 19:39

LioHLioH

805

$endgroup$

add a comment | 

$begingroup$

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?

complexity-theory graph-theory

share|cite|improve this question

asked May 27 at 19:39

LioHLioH

805

$endgroup$

share|cite|improve this question

asked May 27 at 19:39

LioHLioH

805

share|cite|improve this question

asked May 27 at 19:39

LioHLioH

805

asked May 27 at 19:39

LioHLioH

805

asked May 27 at 19:39

LioHLioH

805

2 Answers
2

active

oldest

votes

5

$begingroup$

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.

share|cite|improve this answer

edited May 27 at 21:11

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. But if a graph G, and a witness set of vertices U, are available on the input tape and we just need to verify U, is it not possible to just Iterate on all pairs of vertices (in U) and check (in G) that all corresponding edges exists? And therefore - verify a clique in logspace?
  $endgroup$
  – LioH
  May 27 at 20:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A nondeterministic Turing machine can make nondeterministic moves – in other words, make a guess – and then verify it. But it doesn't get a witness as an input. It turns out that NP can be equivalently defined in terms of witnesses, but this equivalence breaks for NL.
  $endgroup$
  – Yuval Filmus
  May 27 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Now I got it. I was mistakenly thinking the "witnesses definition" can also be applied to NL. Thank you!
  $endgroup$
  – LioH
  May 27 at 21:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you can have a witness based definition for NL. The only difference would be that you have read-only one-way access to the witness tape. (Since we're talking about logspace machines, we have to be careful about the access model to polynomial-sized strings.)
  $endgroup$
  – Robin Kothari
  May 28 at 5:43
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Right, good point.
  $endgroup$
  – Yuval Filmus
  May 28 at 6:25
  

  
  
  
  

add a comment | 

3

$begingroup$

You can iterate over the edges of a graph in logarithmic space, since all that is required in order to do so is a counter up to the number of edges. Note that the hardness of clique and other hard problems in NP does not lie in simple iteration, but in detecting different structures in your input which are not apparent (e.g. a clique of a large enough size).

Additionally, languages decidable by Turing machines which are not able to read the entire input are decidable in constant time, so not being able to iterate over the entire input is not interesting in the standard Turing machine model (as opposed to random access).

share|cite|improve this answer

answered May 27 at 20:10

ArielAriel

10.7k11433

$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/3.0/"u003ecc by-sa 3.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%2f109944%2fnl-iterating-all-edges-of-a-graph-in-log-space%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

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.

share|cite|improve this answer

edited May 27 at 21:11

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. But if a graph G, and a witness set of vertices U, are available on the input tape and we just need to verify U, is it not possible to just Iterate on all pairs of vertices (in U) and check (in G) that all corresponding edges exists? And therefore - verify a clique in logspace?
  $endgroup$
  – LioH
  May 27 at 20:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A nondeterministic Turing machine can make nondeterministic moves – in other words, make a guess – and then verify it. But it doesn't get a witness as an input. It turns out that NP can be equivalently defined in terms of witnesses, but this equivalence breaks for NL.
  $endgroup$
  – Yuval Filmus
  May 27 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Now I got it. I was mistakenly thinking the "witnesses definition" can also be applied to NL. Thank you!
  $endgroup$
  – LioH
  May 27 at 21:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you can have a witness based definition for NL. The only difference would be that you have read-only one-way access to the witness tape. (Since we're talking about logspace machines, we have to be careful about the access model to polynomial-sized strings.)
  $endgroup$
  – Robin Kothari
  May 28 at 5:43
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Right, good point.
  $endgroup$
  – Yuval Filmus
  May 28 at 6:25
  

  
  
  
  

add a comment | 

5

$begingroup$

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.

share|cite|improve this answer

edited May 27 at 21:11

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. But if a graph G, and a witness set of vertices U, are available on the input tape and we just need to verify U, is it not possible to just Iterate on all pairs of vertices (in U) and check (in G) that all corresponding edges exists? And therefore - verify a clique in logspace?
  $endgroup$
  – LioH
  May 27 at 20:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A nondeterministic Turing machine can make nondeterministic moves – in other words, make a guess – and then verify it. But it doesn't get a witness as an input. It turns out that NP can be equivalently defined in terms of witnesses, but this equivalence breaks for NL.
  $endgroup$
  – Yuval Filmus
  May 27 at 21:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Now I got it. I was mistakenly thinking the "witnesses definition" can also be applied to NL. Thank you!
  $endgroup$
  – LioH
  May 27 at 21:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you can have a witness based definition for NL. The only difference would be that you have read-only one-way access to the witness tape. (Since we're talking about logspace machines, we have to be careful about the access model to polynomial-sized strings.)
  $endgroup$
  – Robin Kothari
  May 28 at 5:43
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Right, good point.
  $endgroup$
  – Yuval Filmus
  May 28 at 6:25
  

  
  
  
  

add a comment | 

$begingroup$

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.

share|cite|improve this answer

edited May 27 at 21:11

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

$endgroup$

share|cite|improve this answer

edited May 27 at 21:11

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

answered May 27 at 20:10

Yuval FilmusYuval Filmus

201k15196359

3

$begingroup$

You can iterate over the edges of a graph in logarithmic space, since all that is required in order to do so is a counter up to the number of edges. Note that the hardness of clique and other hard problems in NP does not lie in simple iteration, but in detecting different structures in your input which are not apparent (e.g. a clique of a large enough size).

Additionally, languages decidable by Turing machines which are not able to read the entire input are decidable in constant time, so not being able to iterate over the entire input is not interesting in the standard Turing machine model (as opposed to random access).

share|cite|improve this answer

answered May 27 at 20:10

ArielAriel

10.7k11433

$endgroup$

add a comment | 

3

$begingroup$

You can iterate over the edges of a graph in logarithmic space, since all that is required in order to do so is a counter up to the number of edges. Note that the hardness of clique and other hard problems in NP does not lie in simple iteration, but in detecting different structures in your input which are not apparent (e.g. a clique of a large enough size).

Additionally, languages decidable by Turing machines which are not able to read the entire input are decidable in constant time, so not being able to iterate over the entire input is not interesting in the standard Turing machine model (as opposed to random access).

share|cite|improve this answer

answered May 27 at 20:10

ArielAriel

10.7k11433

$endgroup$

add a comment | 

$begingroup$

You can iterate over the edges of a graph in logarithmic space, since all that is required in order to do so is a counter up to the number of edges. Note that the hardness of clique and other hard problems in NP does not lie in simple iteration, but in detecting different structures in your input which are not apparent (e.g. a clique of a large enough size).

Additionally, languages decidable by Turing machines which are not able to read the entire input are decidable in constant time, so not being able to iterate over the entire input is not interesting in the standard Turing machine model (as opposed to random access).

share|cite|improve this answer

answered May 27 at 20:10

ArielAriel

10.7k11433

$endgroup$

share|cite|improve this answer

answered May 27 at 20:10

ArielAriel

10.7k11433

answered May 27 at 20:10

ArielAriel

10.7k11433

answered May 27 at 20:10

ArielAriel

10.7k11433