Results 1 to 4 of 4

Math Help - SPACE(3 log n)

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    SPACE(3 log n)

    If L is in SPACE(3logn) then L is in P.

    and

    Let TRIPLE = {xxx} Prove that triple is in SPACE(log(n)).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    I assume that L is a language and we are talking about the complexity of a Turing machine that decides membership in this language.

    Suppose a machine M with no input has n states and works on at most m cells. Also, assume that M terminates. How long can it run? If there are k symbols in the tape alphabet, then the number of all possible tapes is k^m. Therefore, the number of all possible configurations (state, tape) is nk^m. If a machine encounters the same configuration twice, then it will loop forever. Thus, the running time is at most nk^m.

    Now assume that a machine M with n states decides a language L and uses at most space 3\log m on inputs of length m. Let's assume for simplicity that \log is to the base k, which is the size of the tape alphabet. Then on an input of size m the running time of M is at most nk^{3\log_k m}=nm^3. So the time complexity is polynomial in m.

    For TRIPLE = {xxx}, do you mean that TRIPLE is a language with a single word? Then I believe it would take constant space and time to decide if a given word is xxx or not, and constant space is also logarithmic.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    Posts
    130
    Quote Originally Posted by emakarov View Post
    I assume that L is a language and we are talking about the complexity of a Turing machine that decides membership in this language.

    Suppose a machine M with no input has n states and works on at most m cells. Also, assume that M terminates. How long can it run? If there are k symbols in the tape alphabet, then the number of all possible tapes is k^m. Therefore, the number of all possible configurations (state, tape) is nk^m. If a machine encounters the same configuration twice, then it will loop forever. Thus, the running time is at most nk^m.

    Now assume that a machine M with n states decides a language L and uses at most space 3\log m on inputs of length m. Let's assume for simplicity that \log is to the base k, which is the size of the tape alphabet. Then on an input of size m the running time of M is at most nk^{3\log_k m}=nm^3. So the time complexity is polynomial in m.

    For TRIPLE = {xxx}, do you mean that TRIPLE is a language with a single word? Then I believe it would take constant space and time to decide if a given word is xxx or not, and constant space is also logarithmic.
    Thank you! that was very clear.

    By TRIPLE = {xxx} i meant {xxx|x is in Sigma*}, sorry.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778
    Proving that some task has a certain complexity is intrinsically a hand-waving activity. Nobody is going to write an actual Turing machine, and even if they did, there is a nontrivial task of proving that the machine behaves as claimed. So, to be good at it one has to belong to an elite society of people who have enough experience and intuition that they mostly give correct answers. Even those people essentially cannot offer a more solid proof than "I can prove that the high-level description of the algorithm has this complexity, and I feel that an implementation in a TM will have this complexity as well".

    So I can only offer some thoughts. Suppose that we have enough space to write the size of input in binary (or maybe 1/3 of the size). To check if the input has the form xxx, we can start from the beginning, remember the symbol there and then shift two times by 1/3 of total size, checking after each shift that we see the same symbol. If yes, then we do the same thing with the second symbol, third, etc.

    I forgot that talking about logarithmic complexity probably involves a TM where the work tape is separate from the input tape, and the space measure is the size of the work tape only. Otherwise, the machine would not be able to visit each cell of the input -- this requires at least linear space and time.

    So, each element of the algorithm (finding the length of the input, division by 3, shift by a given number, etc.) are supposed to work in space C \log n (on work tape) on input of size n. This seems plausible because it never attempts to write some portion (say, of size n/10) of the input to the work tape.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on null space/column space/row space of a matrix
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: December 1st 2011, 01:47 PM
  2. Replies: 5
    Last Post: August 16th 2011, 02:52 PM
  3. Replies: 2
    Last Post: July 8th 2011, 02:16 PM
  4. Replies: 1
    Last Post: January 14th 2011, 09:51 AM
  5. Replies: 15
    Last Post: July 23rd 2010, 11:46 AM

Search Tags


/mathhelpforum @mathhelpforum