 |
 |
 |
Functions on three
variables
Effects concerned with
conditional stop begin to appear when we are computing Boolean functions of
three variables. It easy to see that the circuit complexity of each such
function is no less than 4 and there exist functions (e.g., majority function)
whose circuit complexity equals 4. Let us show that the upper bound for the
average complexity of any three-place Boolean function equals 2.5. For any
three-place Boolean function f we have the following equality
It is easy
to see that the program P
|
|
p1: z = f1(x2,
x3) |
|
|
|
p2: Stop(x1) |
|
|
|
p3: z = f2(x2,
x3) |
|
computes f.
By the definition of a Boolean function that is computed by a straight-line
program with a conditional stop, for P(x) we have
On the three-tuples
(1,0,0), (1,0,1), (1,1,0), and (1,1,1) the program P performs two instructions,
on the other four tuples it performs three instructions. Therefore,
Now let us
show that the average complexity of the majority function
is no less
than 2.5. Let P be a program computing g with minimal average
execution time. If the first stop instruction s1 is the third
instruction in P, then it is obvious that T(P) is no less
than 3. In any program the first instruction must be a functional one and so, we
assume that s1 is the second instruction in P. To end
the proof it is sufficient to show that in P the stop instruction terminates
the computation on at most 4 tuples from the eight ones and, in this case, average
complexity is no less than 2.5. It easy to see that the zero argument is either
the output variable or an independent variable, i.e., the beginning of P
is
|
p1: z = f(x1,
x2) |
z = f(x1, x2) |
|
p2: Stop(z) |
Stop(xi) |
In the
first case if TP(x) = 2, then P(x) = 1. Since
the majority function equals 1 on four tuples from the eight ones, p2
terminates the computation on at most four tuples. In the second case, it is
easy to see that p2 terminates the computation on exactly four
tuples.
|
|
|