Terminology

  All logarithms in this book are to base 2; hence should be read as .

  The notation is used in the formal sense: A problem has size if and only if there exists some constant c and some minimum problem size such that for all , size.

Various symbols are assumed to have the following conventional meanings, unless stated otherwise.