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.

[1] 3.8. Prove that the predicate “x is the binary representation of a com-

posite integer” belongs to NP.

[3] 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

better avoided.)

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

or

10−10

— 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