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
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
Previous Page Next Page