36 1. Classical Computation
The tiling problem requires us to find, for a given set of tile types (con-
taining at most poly(n) types) and for given restrictions, whether or not
there exists a tiling of the (n × n)-square.
Prove that the tiling problem is NP-complete.
 3.8. Prove that the predicate “x is the binary representation of a com-
posite integer” belongs to NP.
 3.9. Prove that the predicate “x is the binary representation of a prime
integer” belongs to NP.
4. Probabilistic algorithms and the class BPP
4.1. Definitions. Amplification of probability. A probabilistic Turing
machine (PTM) is somewhat similar to a nondeterministic one; the differ-
ence is that choice is produced by coin tossing, not by guessing. More for-
mally, some (state, symbol) combinations have two associated actions, and
the choice between them is made probabilistically. Each instance of this
choice is controlled by a random bit. We assume that each random bit is 0
or 1 with probability 1/2 and that different random bits are independent.
(In fact we can replace 1/2 by, say, 1/3 and get almost the same defini-
tion; the class BPP (see below) remains the same. However, if we replace
1/2 by some noncomputable real p, we get a rather strange notion which is
For a given input string a PTM generates not a unique output string,
but a probability distribution on the set of all strings (different values of
the random bits lead to different computation outputs, and each possible
output has a certain probability).
Definition 4.1. Let ε be a constant such that 0 ε 1/2. A predicate
L belongs to the class BPP if there exist a PTM M and a polynomial p(n)
such that the machine M running on input string x always terminates after
at most p(|x|) steps, and
L(x) = 1 ⇒ M gives the answer “yes” with probability ≥ 1 − ε;
L(x) = 0 ⇒ M gives the answer “no” with probability ≤ ε.
In this definition the admissible error probability ε can be, say, 0.49
— the class BPP will remain the same. Why? Assume that the
PTM has probability of error at most ε 1/2. Take k copies of this machine,
run them all for the same input (using independent random bits) and let
them vote. Formally, what we do is applying the majority function MAJ
(see Problem 2.15) to k individual outputs. The “majority opinion” will be