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 suﬃciently

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 coeﬃcients. 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).