20 1. Classical Computation
complexity of f (with respect to the basis A) and is denoted by cA(f). The
value of cA(f) depends on A, but the transition from one finite complete
basis to another changes the circuit complexity by at most a constant factor:
if A1 and A2 are two finite complete bases, then cA1 (f) = O(cA2 (f)) and vice
versa. Indeed, each A2-assignment can be replaced by O(1) A1-assignments
since A1 is a complete basis.
We are interested in asymptotic estimates for circuit complexity (up to
an O(1)-factor); therefore the particular choice of a complete basis is not
important. We use the notation c(f) for the circuit complexity of f with
respect to some finite complete basis.
[2] Problem 2.1. Construct an algorithm that determines whether a given
set of Boolean functions A constitutes a complete basis. (Functions are
represented by tables.)
[2!] Problem 2.2. Let cn be the maximum complexity c(f) for Boolean
functions f in n variables. Prove that
1.99n
cn
2.01n
for sufficiently
large n.
2.2. Circuits versus Turing machines. Any predicate F on
B∗
can be
restricted to strings of fixed length n, giving rise to the Boolean function
Fn(x1,...,xn) = F(x1x2 · · · xn).
Thus F may be regarded as the sequence of Boolean functions F0,F1,F2,... .
Similarly, in most cases of practical importance a (partial) function of
type F :
B∗

B∗
can be represented by a sequence of (partial) functions
Fn :
Bn

Bp(n),
where p(n) is a polynomial with integer coefficients. We
will focus on predicates for simplicity, though.
Definition 2.1. A predicate F belongs to the class P/poly (“nonuniform
P”) if
c(Fn) = poly(n).
(The term “nonuniform” indicates that a separate procedure, i.e., a Boolean
circuit, is used to perform computation with input strings of each individual
length.)
Theorem 2.2. P P/poly.
Proof. Let F be a predicate decidable in polynomial time. We have to
prove that F P/poly. Let M be a TM that computes F and runs in
polynomial time (and therefore in polynomial space). The computation by
M on some input x of length n can be represented as a space-time diagram Γ
that is a rectangular table of size T ×s, where T = poly(n) and s = poly(n).
Previous Page Next Page