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?

$\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, 2023 at 17:39
  • $\begingroup$ $NLOGTIME^P$ should work but I'm not sure $\endgroup$
    – l4m2
    Feb 1, 2023 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$ Feb 1, 2023 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$ Feb 1, 2023 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, 2023 at 10:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.