Introduction to models of computation.

[saga.git] / notation.tex

\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Notation}

{\obeylines\parskip=0pt
\def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
\def\[#1]{[\ref{#1}]}
\n{$\bb R$}{the set of all real numbers}
\n{$\bb N$}{the set of all natural numbers, including 0}
\n{${\bb N}^+$}{the set of all positive integers}
\n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
\n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
\n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
\n{$G-e$}{graph $G$ with edge $e$ removed}
\n{$G+e$}{graph $G$ with edge $e$ added}
\n{$w(e)$}{weight of an edge $e$}
\n{$V(G)$}{set of vertices of a graph~$G$}
\n{$E(G)$}{set of edges of a graph~$G$}
\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
\n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
\n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
\n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
\n{MST}{minimum spanning tree \[mstdef]}
\n{MSF}{minimum spanning forest \[mstdef]}
\n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
\n{$X \choose k$}{a set of all $k$-element subsets of a set~$X$}
\n{$G/e$}{multigraph contraction \[contract]}
\n{$G.e$}{simple graph contraction \[simpcont]}
\n{$\alpha(n)$}{the inverse Ackermann's function}
\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
\n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
\n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
\n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
\n{${\bb E}X$}{expected value of a~random variable~$X$}
\n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
\n{$\log n$}{a binary logarithm of the number~$n$}
\n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
\n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$}
\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]}
}

%--------------------------------------------------------------------------------

\section{Multigraphs and contractions}

Since the formalism of multigraphs is not fixed in the literature, we will
better define it carefully, following \cite{diestel:gt}:

\defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
with the vertices, and $M$ is a mapping $E\mapsto V \cup {V \choose 2}$
which assigns to each edge either a pair of vertices or a single vertex
(if the edge is a loop).

\proclaim{Notation}%
When the meaning is clear from the context, we use our notation originally
defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
consider multigraphs with no multiple edges nor loops and simple graphs to be
the same objects, although they formally differ.

\defn\id{contract}%
Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
produces a multigraph $G/e=(V',E',M')$ such that:
$$\eqalign{
V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
E' &= E(G) - \{e\},\cr
M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
}$$

Sometimes we need contraction for simple graphs as well. It corresponds to performing
the multigraph contraction, unifying parallel edges and deleting loops.

\defn\id{simpcont}%
Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
produces a graph $G.e=(V',E')$ such that:
$$\eqalign{
V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
}$$

%--------------------------------------------------------------------------------

\section{Models of computation}

Traditionally, computer scientists use a~variety of computational models
for a~formalism in which their algorithms are stated. If we were studying
NP-completeness, we could safely assume that all the models are equivalent,
possibly up to polynomial slowdown, which is negligible. In our case, the
differences between good and not-so-good algorithms are on a~much smaller
scale, so we need to replace yardsticks with a~micrometer and define our
computation model carefully.

We would like to keep the formalism close enough to the reality of the contemporary
computers. This rules out Turing machines and similar sequentially addressed
models, but even the remaining models are subtly different. For example, some of them
allow indexing of arrays in constant time, while the others have no such operation
and arrays have to be emulated with pointer structures, requiring $\Omega(\log n)$
time to access a~single element of an~$n$-element array. It is hard to say which
way is superior --- most ``real'' computers have instructions for constant-time
indexing, but on the other hand it seems to be physically impossible to fulfil
this promise with an~arbitrary size of memory. Indeed, at the level of logical
gates, the depth of the actual indexing circuit is logarithmic.

In recent decades, most researchers in the area of combinatorial algorithms
consider two computational models: the Random Access Machine and the Pointer
Machine. The former one is closer to the programmer's view of a~computer,
the latter one is a~little more restricted and ``asymptotically safe.''
We will follow this practice and study our algorithms in both models.

\para
The \df{Random Access Machines (RAMs)} are a~family of computational models
which share the following properties. (For one of the possible formal
definitions, see~\cite{knuth:fundalg}.)

The \df{memory} of the model is represented by an~array of \df{memory cells}
addressed by non-negative integers, each of them containing a~single integer.
The \df{program} is a~sequence of \df{instructions} of two basic kinds: calculation
instructions and control instructions.

\df{Calculation instructions} have two source arguments and one destination
argument, the arguments being either immediate constants (not available
as destination), a~directly addressed memory cell (specified by its number)
or an~indirectly addressed memory cell (its address is stored in a~directly
addressed memory cell).

\df{Control instructions} include branches (to a~specific instruction in
the program), conditional branches (jump if two arguments specified as
in the calculation instructions are equal and so on) and an~instruction
to halt the program.

At the beginning of the computation, the memory contains the input data
in specified memory cells and undefined values in all other cells.
Then the program is executed one instruction at a~time. When it stops,
some specified memory cells are interpreted as the program's output.

\para
In the description of the RAM family, we have omitted several properties
on~purpose, because different members of the family define them differently.
The differences are: the size of the numbers we can calculate with, the time
complexity of a~single instruction, the memory complexity of a~single memory
cell and the repertoire of operations available in calculation instructions.

If we impose no limits on the magnitude of the numbers and we assume that
arithmetic and logical operations work on them in constant time, we get
a~very powerful parallel computer --- we can emulate an~arbitrary number
of processors using arithmetics and suddenly almost everything can be
computed in constant time, modulo encoding and decoding of input and output.
Such models are unrealistic and there are two basic possibilities how to
avoid them:

\numlist\ndotted
\:Keep unlimited numbers, but increase cost of instructions: each instruction
  consumes time proportional to the number of bits of the numbers it processes,
  including memory addresses. Similarly, memory consumption is measured in bits,
  counting not only the values, but also the addresses of the respective memory
  cells.
\:Place a~limit on the size of the numbers. It must not be constant, since
  such machines would be able to address only a~constant amount of memory.
  On the other hand, we are interested in polynomial-time algorithms only, so
  $\Theta(\log n)$-bit numbers, where~$n$ is the size of the input, should be sufficient.
  Then we can keep the cost of instructions and memory cells constant.
\endlist

\FIXME{Mention the word size parameter and cite \cite{hagerup:wordram}}

Both restrictions avoid the problems of unbounded parallelism. The first
choice is theoretically cleaner, but it makes the calculations of time and
space complexity somewhat tedious. What more, these calculations usually result in both
complexities being exactly $\Theta(\log n)$ times higher that with the second
choice. This does not hold in general (consider a~program which uses many
small numbers and $\O(1)$ large ones), but it is true for the algorithms we are
interested in. Therefore we will always assume that the operations have unit
cost and we make sure that all numbers are limited either by $\O(\log n)$ bits
or by the size of numbers on the algorithm's input, whatever is bigger.

As for the choice of RAM operations, the following three variants are usually
considered:

\itemize\ibull
\:\df{Word-RAM} --- allows the ``C-language operators'', i.e., addition,
  subtraction, multiplication, division, remainder, bitwise {\sc and,} {\sc or,} exclusive
  {\sc or} ({\sc xor}) and negation ({\sc not}).
\:\df{${\rm AC}^0$-RAM} --- allows all operations from the class ${\rm AC}^0$, i.e.,
  those computable by constant-depth polynomial-size boolean circuits with unlimited
  fan-in and fan-out. This includes all operations of the Word-RAM except for multiplication,
  division and remainders, and also many other operations like computing the Hamming
  weight (number of bits set in a~given number).
\:Both restrictions at once.
\endlist

As shown by Thorup in \cite{thorup:aczero}, for the usual purposes the first two choices
are equivalent, while the third one is strictly weaker. We will therefore use the
Word-RAM instruction set, mentioning differences of ${\rm AC}^0$-RAM where necessary.

\nota
When speaking of the \df{RAM model,} we implicitly mean the version with limited numbers,
unit cost of operations and memory cells and the instruction set of the Word-RAM.
This corresponds to the usage in recent algorithmic literature, although the
authors rarely mention the details.


\endpart