\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{$\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
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
projects / saga.git / blobdiff