<p>Savitch's theorem shows that NSPACE(<span class="math-container">$S(n)$</span>) <span class="math-container">$\subseteq$</span> SPACE(<span class="math-container">$S(n)^2$</span>), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be replaced by advice strings in a similar situation?</p>

<p>Especially, I would like to ask about "L/quasipoly vs NL/poly". If L/quasipoly <span class="math-container">$\supset$</span> NL/poly is proved, is this a new result?</p>

<p>(Here, L/quasipoly means (informally) L with quasipolynomial size advice strings.)</p>

<p>[Supplementary explanations]</p>

<p>Currently, I think that I may be able to prove that polynomial-size nondeterministic branching programs can be simulated by quasipolynomial-size <span class="math-container">$O(\log n)$</span>-width boolean circuits.</p>

CC BY-SA 4.0
2018-10-02T08:09:45.470Z
As far as I can see, an L machine can only access a polynomial part of the advice string, hence trivially L/quasipoly=L/poly. If this is not what you meant, you should specify the model more precisely.
Emil Jeřábek
CC BY-SA 4.0
2018-10-02T08:38:20.587Z
I'm not an expert for TM, but I have understood P includes L. Can L machine really only access a polynomial part of the advice string? For example, L machine can read the advice string one by one from left to right. Is this wrong?
Hiroki Morizumi
CC BY-SA 4.0
2018-10-02T10:21:20.340Z
So, the advice model is just a read-only tape, with the machine having no way of keeping track of the current position? I see that the TM is now not limited to polynomially many configurations, hence it can also run for superpolynomial time, eliminating my objection. But now I’m worried if this does not give the TM polylogarithmic space in a sneaky way, by abusing the head position to encode polylogarithmically many bits.
Emil Jeřábek
CC BY-SA 4.0
2018-10-02T12:24:47.593Z
I probably recognized my misunderstanding. "L/quasipoly" is my fault, but I still would like to be working on this problem. Please let me edit the question.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-02T17:18:35.363Z
While I again think that L/quasipoly may be meaningful, I stop editting, which causes more confusion.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-02T20:43:53.953Z
How about making the advice tape one-way? Mini-exercise: Even with this def, L/exp contains every language.
domotorp
CC BY-SA 4.0
2018-10-03T00:20:32.747Z
@domotorp: Thank you very much. An answer to mini-exercise: The advice string contains all acceptable inputs in a line. O(logn) space is enough to check it.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-03T00:35:51.600Z
I would be very happy if I heard positive comments from more professors to my thought that L/quasipoly is meaningful.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-03T01:25:30.410Z
Another issue to specify: if the advice tape is not one-way then are you allowed to move the reading head beyond the end of the advice?
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-10-03T01:50:45.860Z
@Bjørn Kjos-Hanssen: The current critical issue is whether L/quasipoly is meaningful or not. So, I think that your comment is not critical if the advice tape can be used as one-way.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-04T02:20:40.120Z
I reedit my question to (almost) the first one. Very sorry for bad edit sequence. If someone thinks L/quasipoly=L/poly, please kindly comment again.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-04T02:23:35.430Z
@Emil Jeřábek (a few days ago): The number of current head positions of the advice tape makes superpolynomial configurations. The TM doesn't need to keep track of the current position.
Hiroki Morizumi
<cc.complexity-theory>
L/quasipoly vs NL/poly
Hiroki Morizumi
# L/quasipoly vs NL/poly

(Asked by: username_0 on 2018-10-02)

Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be replaced by advice strings in a similar situation?

Especially, I would like to ask about "L/quasipoly vs NL/poly". If L/quasipoly $\supset$ NL/poly is proved, is this a new result?

(Here, L/quasipoly means (informally) L with quasipolynomial size advice strings.)

[Supplementary explanations]

Currently, I think that I may be able to prove that polynomial-size nondeterministic branching programs can be simulated by quasipolynomial-size $O(\log n)$-width boolean circuits.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: As far as I can see, an L machine can only access a polynomial part of the advice string, hence trivially L/quasipoly=L/poly. If this is not what you meant, you should specify the model more precisely.  
> **username_0**: I'm not an expert for TM, but I have understood P includes L. Can L machine really only access a polynomial part of the advice string? For example, L machine can read the advice string one by one from left to right. Is this wrong?  
> **username_1**: So, the advice model is just a read-only tape, with the machine having no way of keeping track of the current position? I see that the TM is now not limited to polynomially many configurations, hence it can also run for superpolynomial time, eliminating my objection. But now I’m worried if this does not give the TM polylogarithmic space in a sneaky way, by abusing the head position to encode polylogarithmically many bits.  
> **username_0**: I probably recognized my misunderstanding. "L/quasipoly" is my fault, but I still would like to be working on this problem. Please let me edit the question.  
> **username_0**: While I again think that L/quasipoly may be meaningful, I stop editting, which causes more confusion.  
> **username_2**: How about making the advice tape one-way? Mini-exercise: Even with this def, L/exp contains every language.  
> **username_0**: @domotorp: Thank you very much. An answer to mini-exercise: The advice string contains all acceptable inputs in a line. O(logn) space is enough to check it.  
> **username_0**: I would be very happy if I heard positive comments from more professors to my thought that L/quasipoly is meaningful.  
> **username_3**: Another issue to specify: if the advice tape is not one-way then are you allowed to move the reading head beyond the end of the advice?  
> **username_0**: @Bjørn Kjos-Hanssen: The current critical issue is whether L/quasipoly is meaningful or not. So, I think that your comment is not critical if the advice tape can be used as one-way.  
> **username_0**: I reedit my question to (almost) the first one. Very sorry for bad edit sequence. If someone thinks L/quasipoly=L/poly, please kindly comment again.  
> **username_0**: @Emil Jeřábek (a few days ago): The number of current head positions of the advice tape makes superpolynomial configurations. The TM doesn't need to keep track of the current position.  

---

## 0 answers

