22 1. Classical Computation

Remark 2.1. The class P/poly is bigger than P. Indeed, let ϕ : N → B

be an arbitrary function (maybe even a noncomputable one). Consider the

predicate Fϕ such that Fϕ(x) = ϕ(|x|), where |x| stands for the length of

string x. The restriction of Fϕ to strings of length n is a constant function

(0 or 1), so the circuit complexity of (Fϕ)n is O(1). Therefore Fϕ for any ϕ

belongs to P/poly, although for a noncomputable ϕ the predicate Fϕ is not

computable and thus does not belong to P.

Remark 2.2. That said, P/poly seems to be a good approximation of P

for many purposes. Indeed, the class P/poly is relatively small: out of

22n

Boolean functions in n variables only

2poly(n)

functions have polynomial

circuit complexity (see solution to Problem 2.2). The difference between

uniform and nonuniform computation is more important for bigger classes.

For example, EXPTIME, the class of predicates decidable in time

2poly(n),

is a nontrivial computational class. However, the nonuniform analog of this

class includes all predicates!

The arguments used to prove Theorem 2.2 can also be used to prove the

following criterion:

Theorem 2.3. F belongs to P if and only if these conditions hold:

(1) F ∈ P/poly;

(2) the functions Fn are computed by polynomial-size circuits Cn with the

following property: there exists a TM that for each positive integer n

runs in time poly(n) and constructs the circuit Cn.

A sequence of circuits Cn with this property is called polynomial-time uni-

form.

Note that the TM mentioned in (2) is not running in polynomial time

since its running time is polynomial in n but not in log n (the number of bits

in the binary representation of n). Note also that we implicitly use some

natural encoding for circuits when saying “TM constructs a circuit”.

Proof. ⇒ The circuit for computing Fn constructed in Theorem 1.2 has

regular structure, and it is clear that the corresponding sequence of assign-

ments can be produced in polynomial time when n is known.

⇐ This is also simple. We compute the size of the input string x,

then apply the TM to construct a circuit C|x| that computes F|x|. Then

we perform the assignments indicated in C|x|, using x as the input, and

get F(x). All these computations can be performed in polynomial (in |x|)

time.

[1] Problem 2.3. Prove that there exists a decidable predicate that be-

longs to P/poly but not to P.