# Complexity of comparison unary>binary

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$.)
• 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}$ – user6973 May 21 '17 at 11:35
• 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. – Emil Jeřábek Feb 1 '18 at 13:52