Hard wiring? - for the brainiacs on this forum

[manni]

Hi i have a technical question that i would like to put to you: here it is:

or can anyone please explain to me what it means to "hardwire" in this context.

1) for each k > 0 describe how to construct a deterministic program Mk that computes the function F : Bᵏ → B that takes the value 1 if and only if a majority of its inputs are 1. The size of Mk should be polynomial in K (Program should first sort its inputs on 1s and 0s)

2) given n in the natural numbers N, using chernoff bounds, explain how a program P computing a function F : Bᵏ → B can be transformed to a program Q such that

Probability(Q(b1,.......,bk))= F(b1,......,bk)) >= 1 - (2 ⁻ ⁿ) for all b1,...,bk in B. The size of Q should be bounded by a polynomial in n and the size of P.

3) Show that for each k > 0 and function F : Bᵏ → B, if there is a program P that computes F then there is a deterministic program Q that computes F such that the size of Q is polynomial in the size of P (use answer to part 2 and "hardwire" a suitable valuation of the random inputs.

[Moschops]

In this context, it means don't use actual random values; work out what values the random inputs would have to be to get the effect needed, and use those values instead of random values, written directly into your code where the random values would have been.

[manni]

Thanks

so you mean, fix a value of the input. and use this value to analyse and demonstrate that the time complexity of Q is polynomial in P?