1
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • $\begingroup$ Seems some issue, brute-forcing all branches of NLOGTIME may need poly time, but it's the main idea $\endgroup$
    – l4m2
    Jan 31 at 17:39
  • $\begingroup$ $NLOGTIME^P$ should work but I'm not sure $\endgroup$
    – l4m2
    Feb 1 at 1:29
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Feb 1 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Feb 1 at 8:40
  • $\begingroup$ $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 $\endgroup$
    – l4m2
    Feb 1 at 10:05

0

Reset to default

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.