1
$\begingroup$

I have two questions on Kaveh's answer to Definition of uniform boolean circuit :

  1. Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a sequence of 1's repeated n times, but unary encoding is a sequence of 1's and ends with 0 there is no power of 1 that gives 0... So how is $1^n$ a unary encoding?
  2. Why do we use a unary encoding and not the binary encoding of n? what happens if we use binary instead?
$\endgroup$

1 Answer 1

3
$\begingroup$

Here is the binary encoding of 5: $$101$$ And here is its unary encoding: $$11111$$ Hopefully the difference is apparent.

Let's see what happens if we switch to binary encoding in the context of the linked question. Given the binary encoding of $n$, we need to produce a circuit, operating on $n$ bits, in logspace, and so in polynomial time. How much time do we have? The binary encoding of $n$ has length roughly $\log n$, so we have time $O(\log^C n)$, which isn't enough to produce a circuit which reads all input bits.

In contrast, if we use unary encoding, then the length of the input is $n$, and so we have time $O(n^C)$, which is more reasonable (in addition, we are only allowed to use $O(\log n)$ space).

$\endgroup$
1
  • $\begingroup$ Oh, I was a bit confused because in the definition I know of unary encoding 5 would be 111110 (five 1's followed by a terminal 0) I had a doubt why the 0 is omitted here. Thanks for clarifying $\endgroup$
    – user206904
    Commented Mar 14, 2021 at 16:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.