Skip to main content
deleted 60 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

In the first answerI have two questions on a circuit uniformity question here: Kaveh's answer to Definition of uniform boolean circuit

I have 2 questions  :

  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?

Thanks in advance

In the first answer on a circuit uniformity question here: Definition of uniform boolean circuit

I have 2 questions:

  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?

Thanks in advance

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?
Source Link
user206904
  • 320
  • 1
  • 12

What is uniformity in Boolean circuits exactly?

In the first answer on a circuit uniformity question here: Definition of uniform boolean circuit

I have 2 questions:

  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?

Thanks in advance