<p><a href="https://en.wikipedia.org/wiki/Low_(complexity)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Low_(complexity)</a></p>
<blockquote>
<p>Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed under complement, but is not low for itself.</p>
</blockquote>
<p>NLOGTIME can negate boolean result, it just can't pass whole input into oracle, and passible size is log(n), on which size it needn't an oracle. NLOGTIME is also not closed under complement due to EQUALITY.</p>
<p>Is it some misunderstanding or wrong wiki?</p>

CC BY-SA 4.0
2023-01-31T17:39:06.360Z
Seems some issue, brute-forcing all branches of NLOGTIME may need poly time, but it's the main idea
l4m2
CC BY-SA 4.0
2023-02-01T01:29:21.650Z
$NLOGTIME^P$ should work but I'm not sure
l4m2
CC BY-SA 4.0
2023-02-01T08:36:21.853Z
The statement on Wikipedia is *informal* (to begin with, there is no uniform way how to relativize arbitrary classes with oracles), and obviously was not written with such small classes in mind. The *real* question is what should be a sensible definition of relativized NLOGTIME so that it can make oracle queries of size proportional to the size of the input. Note that, for example, the standard definition of (uniform) relativized $\mathrm{AC}^0$ does that; $\mathrm{AC}^0$ equals the LOGTIME hierarchy (i.e., alternating LOGTIME with $O(1)$ alternations), hence NLOGTIME is its special case.
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T08:40:27.980Z
In any case, the “correct” answer should be that NLOGTIME is not low for itself, and the smallest class $C$ such that $\mathrm{NLOGTIME}^C=C$ should be $\mathrm{AC}^0$. If your definition of NLOGTIME with oracles does not yield this conclusion, the definition is wrong.
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T10:05:29.087Z
$NLOGTIME^{P^{NLOGTIME^P}}$ should be $NLOGTIME^P$, right? and $NLOGTIME^C$ still can't pass all input into the $C$. Unless passing all input into oracle is somehow enabled by other way @EmilJeřábek
l4m2
CC BY-SA 4.0
2023-02-01T10:07:02.193Z
That’s my point: you *have to* enable passing all input (and other such things) to the oracle. Otherwise the definition is defective.
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T10:11:56.573Z
The common definition where oracle queries are written sequentially on an oracle tape is only appropriate for classes powerful enough to read or write sequentially such long strings. LOGTIME and similar classes cannot even read the input sequentially, and (in case of function problems) cannot write the output sequentially. It is completely unreasonable to ask them to write oracle queries sequentially. The machine reads the input bit by bit by writting its position on an index tape, and if it has output, it is produced dually by reading the output bit position from an output index tape, and ...
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T10:16:35.343Z
... computing this bit. Oracle access should be made in a similar way. What suggests itself is to provide the oracle with a call-back mechanism: after you signal the oracle you want it to compute something, the oracle can write back oracle query indices to a special tape, and you reply with the corresponding bit of the intended oracle query. What is less clear is how to account for the computation of these call backs in the time of the machine; you still have to treat the oracle as a black box, so the right model is that it potentially asks for all query bits in parallel. That is, for a ...
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T10:19:47.193Z
... (N)LOGTIME machine, the *maximum* time spent on producing any query bit should be $O(\log n)$. I’m not sure what to do with nondeterminism, as this just make a whole mess; perhaps just require the query bits to be answered deterministically. I’m also not sure if it’s ok that the machine can make an unbounded number of oracle calls during one run (allbeit of shorter size); if this somehow becomes a problem, make an $O(1)$ bound on the number of oracle calls part of the definition.
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T11:42:28.323Z
@EmilJeřábek [This](https://cs.stackexchange.com/a/128470/77633) claims oracle without ability to read input, and allowing it makes linear not self-low, and allowing O(1) read of whole input is also weird
l4m2
CC BY-SA 4.0
2023-02-01T11:58:59.353Z
That answer is about NL (nodeterministic *logspace*) rather than NLOGTIME, and it is unequivocally *wrong*, as (unlike my suggestions above) the definition of relativized NL is perfectly standard, and *does* allow writing queries as long as the input. In this case no complicated constructions are necessary, you simply treat the oracle tape as write-only, and do not count it towards the space usage of the algorithm, just like it is done with the input and output tapes. You need to limit the computation to polynomial time, though, as this is no longer guaranteed.
Emil Jeřábek
CC BY-SA 4.0
2023-02-01T12:00:43.173Z
($\mathrm{NL^{NL}=NL}$ *is* true, but for nontrivial reasons, namely Immerman–Szelepcsényi.)
Emil Jeřábek
<complexity-classes><oracles>
Is NLOGTIME self-low?
l4m2
# Is NLOGTIME self-low?

(Asked by: username_0 on 2023-01-31)

<https://en.wikipedia.org/wiki/Low_(complexity)>

> Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed under complement, but is not low for itself.

NLOGTIME can negate boolean result, it just can't pass whole input into oracle, and passible size is log(n), on which size it needn't an oracle. NLOGTIME is also not closed under complement due to EQUALITY.

Is it some misunderstanding or wrong wiki?

**Tags:** complexity-classes, oracles

> **Comments:**
> **username_0**: Seems some issue, brute-forcing all branches of NLOGTIME may need poly time, but it's the main idea  
> **username_0**: $NLOGTIME^P$ should work but I'm not sure  
> **username_1**: The statement on Wikipedia is *informal* (to begin with, there is no uniform way how to relativize arbitrary classes with oracles), and obviously was not written with such small classes in mind. The *real* question is what should be a sensible definition of relativized NLOGTIME so that it can make oracle queries of size proportional to the size of the input. Note that, for example, the standard definition of (uniform) relativized $\mathrm{AC}^0$ does that; $\mathrm{AC}^0$ equals the LOGTIME hierarchy (i.e., alternating LOGTIME with $O(1)$ alternations), hence NLOGTIME is its special case.  
> **username_1**: In any case, the “correct” answer should be that NLOGTIME is not low for itself, and the smallest class $C$ such that $\mathrm{NLOGTIME}^C=C$ should be $\mathrm{AC}^0$. If your definition of NLOGTIME with oracles does not yield this conclusion, the definition is wrong.  
> **username_0**: $NLOGTIME^{P^{NLOGTIME^P}}$ should be $NLOGTIME^P$, right? and $NLOGTIME^C$ still can't pass all input into the $C$. Unless passing all input into oracle is somehow enabled by other way @EmilJeřábek  
> **username_1**: That’s my point: you *have to* enable passing all input (and other such things) to the oracle. Otherwise the definition is defective.  
> **username_1**: The common definition where oracle queries are written sequentially on an oracle tape is only appropriate for classes powerful enough to read or write sequentially such long strings. LOGTIME and similar classes cannot even read the input sequentially, and (in case of function problems) cannot write the output sequentially. It is completely unreasonable to ask them to write oracle queries sequentially. The machine reads the input bit by bit by writting its position on an index tape, and if it has output, it is produced dually by reading the output bit position from an output index tape, and ...  
> **username_1**: ... computing this bit. Oracle access should be made in a similar way. What suggests itself is to provide the oracle with a call-back mechanism: after you signal the oracle you want it to compute something, the oracle can write back oracle query indices to a special tape, and you reply with the corresponding bit of the intended oracle query. What is less clear is how to account for the computation of these call backs in the time of the machine; you still have to treat the oracle as a black box, so the right model is that it potentially asks for all query bits in parallel. That is, for a ...  
> **username_1**: ... (N)LOGTIME machine, the *maximum* time spent on producing any query bit should be $O(\log n)$. I’m not sure what to do with nondeterminism, as this just make a whole mess; perhaps just require the query bits to be answered deterministically. I’m also not sure if it’s ok that the machine can make an unbounded number of oracle calls during one run (allbeit of shorter size); if this somehow becomes a problem, make an $O(1)$ bound on the number of oracle calls part of the definition.  
> **username_0**: @EmilJeřábek [This](https://cs.stackexchange.com/a/128470/77633) claims oracle without ability to read input, and allowing it makes linear not self-low, and allowing O(1) read of whole input is also weird  
> **username_1**: That answer is about NL (nodeterministic *logspace*) rather than NLOGTIME, and it is unequivocally *wrong*, as (unlike my suggestions above) the definition of relativized NL is perfectly standard, and *does* allow writing queries as long as the input. In this case no complicated constructions are necessary, you simply treat the oracle tape as write-only, and do not count it towards the space usage of the algorithm, just like it is done with the input and output tapes. You need to limit the computation to polynomial time, though, as this is no longer guaranteed.  
> **username_1**: ($\mathrm{NL^{NL}=NL}$ *is* true, but for nontrivial reasons, namely Immerman–Szelepcsényi.)  

---

## 0 answers

