Notation

∨ disjunction (logical OR)

∧ conjunction (logical AND)

¬ negation

⊕ addition modulo 2 (and also the direct sum

of linear subspaces)

❤❡

controlled NOT gate (p. 62)

blank symbol in the alphabet of a Turing machine

δ(·, ·) transition function of a Turing machine

δjk Kronecker symbol

χS (·) characteristic function of the set S

f⊕ invertible function corresponding to the

Boolean function f (p. 61)

xn−1 · · · x0 number represented by binary digits xn−1,...,x0

gcd(x, y) greatest common divisor of x and y

a mod q residue of a modulo q

a

b

representation of the rational number a/b in the

form of an irreducible fraction

a | b a divides b

a ≡ b (mod q) a is congruent to b modulo q

A ⇒ B A implies B

A ⇔ B A is logically equivalent to B

L1 ∝ L2 Karp reduction of predicates

(L1 can be reduced to L2 (p. 30))

x the greatest integer not exceeding x

x the least integer not greater than x

xi