What is the smallest widely-known complexity class to which $$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\land & j\ \text{is a binary encoding of a nonnegative integer}\ \hat\jmath\\\land & \hat\imath>\hat\jmath\end{array}\right\}$$ belongs to? The language is probably nonregular, but definitely in DLOGSPACE. Does this language lie in any smaller well-known class?


The problem is in coNLOGTIME, for example using the following algorithm. As is well known, one can determine the length of input $n$ in binary in DLOGTIME. Then, read off at most $\log n$ bits from the end of the input to find $j$ (if it is longer, reject). This also determines $i=n-1-\lfloor\log(j+1)\rfloor$ (I am assuming one character for the separator), so it remains to check that $i>j$, and that the beginning of the input is indeed a valid unary encoding: only the last part uses nondeterminism. (That is, the problem would be in DLOGTIME if it were defined so that any string of length $i$ counted as a unary encoding of $i$.)

  • $\begingroup$ Even if j is longer, it can still remain to check that j's most significant bits are not all zero. $\hspace{1.22 in}$ $\endgroup$ – user6973 May 21 '17 at 11:35
  • $\begingroup$ The most significant bit of binary representation is nonzero by definition. $\endgroup$ – Emil Jeřábek May 21 '17 at 11:56
  • $\begingroup$ (Not that it would make a difference. The complexity stays coNLOGTIME even if we allow leading zeros.) $\endgroup$ – Emil Jeřábek May 21 '17 at 13:11
  • $\begingroup$ There are several definitions of logtime computations (cf. Reagan and Vollmer, Gap-languages and log-time complexity classes, 1997). Which definition are you using? $\endgroup$ – user48415 Jan 31 '18 at 23:59
  • 1
    $\begingroup$ The standard one ("proviso $\mathcal U$"). It is called standard for a reason. The "Ruzzo" convention effectively requires two extra alternations for each query, hence it is unsuitable for low-depth fragments of AC^0 as here. I've never ever seen anyone use the "Sipser" convention, it seems to be an overcomplicated way of restricting the number of queries to $O(1)$ per computation path, which makes it unsuitable for low-depth fragments of AC^0 for exactly the same reason as before. $\endgroup$ – Emil Jeřábek Feb 1 '18 at 13:52

It is in uniform AC0 = AltTime(O(1), O(lg n)). Bit(j,i) -- the i-th bit of binary representation of unary number j -- is in uniform AC0. See e.g. Cook and Nguyen, Logical Foundation of Computational Complexity, 2010. Comparison then is just two log bounded quantifiers.

  • $\begingroup$ You mean AltTime(O(1),O(log n)). $\endgroup$ – Emil Jeřábek May 21 '17 at 8:33
  • $\begingroup$ Whatt is AltTime(f,g)? $\endgroup$ – user48418 Feb 1 '18 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy