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 such that Fϕ(x) = ϕ(|x|), where |x| stands for the length of
string x. The restriction of to strings of length n is a constant function
(0 or 1), so the circuit complexity of (Fϕ)n is O(1). Therefore for any ϕ
belongs to P/poly, although for a noncomputable ϕ the predicate 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.
Previous Page Next Page