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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 2 '18 at 8:09
  • $\begingroup$ 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? $\endgroup$ – Hiroki Morizumi Oct 2 '18 at 8:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 2 '18 at 10:21
  • $\begingroup$ 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. $\endgroup$ – Hiroki Morizumi Oct 2 '18 at 12:24
  • 2
    $\begingroup$ How about making the advice tape one-way? Mini-exercise: Even with this def, L/exp contains every language. $\endgroup$ – domotorp Oct 2 '18 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.