Skip to main content
Computer Science

Return to Question

added 623 characters in body; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

$log $\log n$ lowerboundlower bound for space complexity

I am currently reading “AroraArora and BarakBarak's , Computational Complexity”;Computational complexity. In chapterChapter 4 (Space complexity)  , they say the following:

Since the TM's work tapes are separated from its input tape, it makes sense to consider space-bounded machines that use space less than the input length, namely, $S(n) < n$. This is in contrast to time-bounded computation, where $\mathbf{DTIME}(T(n))$ for $T(n) < n$ does not make much sense since the TM does not have enough time to read the entire input. We will require however than $S(n) > \log n$ since the work tape has length $n$ [my highlight], and we would like the machine to at least be able to "remember" the index of the cell of the input tape that it is currently reading.

I doubt that onethe highlighted statement is true:. enter image description here

AsAs you can see  , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” Could

“Since the work tape has length $n$”

could not be true and it should be: “Since the input tape has length $n$”

“Since the input tape has length $n$”

If this is not a typo, so i confuseI am confused why it mentionmentions that the work tape has length of $n$, as we know that it may have smaller length ?.

$log n$ lowerbound for space complexity

I currently reading “Arora and Barak , Computational Complexity”; In chapter 4 (Space complexity)  , I doubt that one statement is true: enter image description here

As you can see  , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” Could not be true and it should be: “Since the input tape has length $n$”

If this is not a typo, so i confuse why it mention that work tape has length of $n$ as we know it may have smaller length ?

$\log n$ lower bound for space complexity

I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following:

Since the TM's work tapes are separated from its input tape, it makes sense to consider space-bounded machines that use space less than the input length, namely, $S(n) < n$. This is in contrast to time-bounded computation, where $\mathbf{DTIME}(T(n))$ for $T(n) < n$ does not make much sense since the TM does not have enough time to read the entire input. We will require however than $S(n) > \log n$ since the work tape has length $n$ [my highlight], and we would like the machine to at least be able to "remember" the index of the cell of the input tape that it is currently reading.

I doubt that the highlighted statement is true. As you can see, it says that to be able to remember the indexes of input tape, so

“Since the work tape has length $n$”

could not be true and it should be

“Since the input tape has length $n$”

If this is not a typo, I am confused why it mentions that the work tape has length of $n$, as we know that it may have smaller length.

added 2 characters in body
Source Link
Omid Yaghoubi
Omid Yaghoubi
  • 368
  • 1
  • 11

I currently reading “Arora and Barak , Computational Complexity”; In chapter 4 (Space complexity) , I doubt that one statement is true: enter image description here

As you can see , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” CouldntCould not be true and it should be: “Since the input tape has length $n$”

If this is not a typo, so i confuse why it mention that work tape has length of $n$ as we know it may have smaller length ?

I currently reading “Arora and Barak , Computational Complexity”; In chapter 4 (Space complexity) , I doubt that one statement is true: enter image description here

As you can see , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” Couldnt be true and it should be: “Since the input tape has length $n$”

If this is not a typo, so i confuse why it mention that work tape has length of $n$ as we know it may have smaller length ?

I currently reading “Arora and Barak , Computational Complexity”; In chapter 4 (Space complexity) , I doubt that one statement is true: enter image description here

As you can see , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” Could not be true and it should be: “Since the input tape has length $n$”

If this is not a typo, so i confuse why it mention that work tape has length of $n$ as we know it may have smaller length ?

Source Link
Omid Yaghoubi
Omid Yaghoubi
  • 368
  • 1
  • 11

$log n$ lowerbound for space complexity

I currently reading “Arora and Barak , Computational Complexity”; In chapter 4 (Space complexity) , I doubt that one statement is true: enter image description here

As you can see , it says that to be able to remember the indexes of input tape, so “Since the work tape has length $n$” Couldnt be true and it should be: “Since the input tape has length $n$”

If this is not a typo, so i confuse why it mention that work tape has length of $n$ as we know it may have smaller length ?