polysize description of truth table

#1 08-25-2008, 02:09 AM

Say there is a boolean circuit B with n number of inputs. The number
of gates in the boolean circuit is polynomial in the size of n. Let O
be the output string where O is the sequence of 0s and 1s obtained by
traversing down the output column of the truth table of B.

Let B1 be the boolean circuit which takes in the nth "1" in the output
string and returns the position of the nth "1" bit in the output
string or returns some fixed value if the output string contains only
n-1 "1" bits.

Will B1 always be polynomial in the size of n (n being the number of
inputs to B)?

#2 08-25-2008, 02:11 AM

On Aug 25, 2:09*am, "sidg...@gmail.com" <sidg...@gmail.com> wrote:
> Say there is a boolean circuit B with n number of inputs. The number
> of gates in the boolean circuit is polynomial in the size of n. Let O
> be the output string where O is the sequence of 0s and 1s obtained by
> traversing down the output column of the truth table of B.
>
> Let B1 be the boolean circuit which takes in the nth "1" in the output
> string and returns the position of the nth "1" bit in the output
> string or returns some fixed value if the output string contains only
> n-1 "1" bits.
>
> Will B1 always be polynomial in the size of n (n being the number of
> inputs to B)?

Clarification: B1 is the minimal circuit possible for its
corresponding truth table.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode