Computer Science Asked by yankovs on October 21, 2021
I was wondering if it can be said that $mbox{NL}^mbox{NL}=mbox{NL}$. That is, a decision problem $S$ can be decided using a nondeterministic TM using logarithmic space with oracle calls to $S’in mbox{NL}$ iff $Sin mbox{NL}$.
My intuition is yes, because if $S’in mbox{NL}$ then there is a NDTM $M$ that decides it in logarithmic space. And so one can use the NDTM $M’$ for $S$ but every oracle call will be simulated on $M$, preserving the logarithmic space constraint.
I am not sure if this approach is correct, and if it is, how to formally explain such an algorithm for the simulation.
(Sorry, it's not my area, so I'm not confident, but it should be correct)
Yes. Moreover, you can assume that your oracle requires memory which depends linearly on the input size.
One way to define oracles is to assume that you have a main tape $T_1$ (or many such tapes) and a special tape $T_2$ such that you can write on this tape, and in one step solve the problem on this tape. This happens when we arrive into a special state $Q$, and after oracle computation it changes into new state $R$.
Machine construction: Let $M$ be a "main" TM. Let $M'$ be a TM for our oracle with starting state $S$ and final state $F$. I assume that machines' sets of states $S_M$ and $S_{M'}$ are disjoint. Then we build an oracle-less machine the following way:
Our new states are the following: $(S_M setminus {Q}) cup (S_{M'} setminus {F})$.
When we work on $T_1$ (current state is in $S_M$), our rules ignore symbols on $T_2$ and also don't update $T_2$ in any way. Similarly when we work with $T_2$.
When we should arrive at $Q$ in $M$, we instead arrive at $S$ (starting state of $M'$). Similarly, when we should arrive at $F$ in $M'$, we instead arrive at $R$.
Answering your question: If $M$ requires logarithmic space, and $M'$ requires linear space, then the resulting machine is in $NL$:
Answered by user114966 on October 21, 2021
It's not quite as simple. Calls to oracle have a "magic" quality of taking only one unit of time. Even if NL can simulate the oracle calls, these simulated invocations of the oracle can take more resources than is needed by the oracle machine. To prove these classes equal you need to prove that calls to the oracle do not improve performance in the computational complexity sense because producing the input to the oracle already requires sufficient resources that the oracle machine cannot use this "magic" to get improved performance.
Answered by Esa Pulkkinen on October 21, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP