TransWikia.com

can it be said that NL^NL = NL?

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.

2 Answers

(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$:

  • We only use logarithmic space on $T_1$.
  • During execution of $M$ (when we work on $T_1$), the algorithm can write only $O(log n)$ memory on $T_2$ (since we assume that $M$ requires logarithmic amount of memory). After that, since $M'$ can use memory which linearly depends on the input size, it also requires $O(log n)$ memory. After execution of $M'$, $T_2$ has $O(1)$ size.

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP