andreev's function
let 
. the function 
(Andreev's function) is defined as as the function that receives as input a truth table of a function 
and 
strings 
of length 
and computes
notice that the length of its input is 
, since we have variables of length 
, and we need an extra bits to represent the function 
.
. the function (Andreev's function) is defined as as the function that receives as input a truth table of a function and strings of length and computesnotice that the length of its input is , since we have variables of length , and we need an extra bits to represent the function .
by boolean_formula.html there exists such that 
, if we set it to a constant in the input of we get
where 
is a substitution that turns the bits of constant, then we get
such that , if we set it to a constant in the input of we getwhere is a substitution that turns the bits of constant, then we get