number encoding effect on complexity

Question

I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the paragraph in the first chapter, Page 3, first paragraph. I have attached the paragraph below:

An important caveat concerning random-access and pointer machines is that if the machine can manipulate numbers of arbitrary size in constant time, it can perform hidden parallel computation by encoding several numbers into one. There are two ways to prevent this. Instead of counting each operation as one step (the uniform cost measure), we can charge for an operation a time proportional to the number of bits needed to represent the operands (the logarithmic cost measure). Alternatively we can limit the size of the integers we allow to those representable in a constant times log n bits, where n is a measure of the input size, and restrict the operations we allow on real numbers. We shall generally use the latter approach; all our algorithms are implementable on a random-access or pointer machine with integers of size at most n for some small constant c with only comparison, addition, and sometimes multiplication of input values allowed as operations on real numbers, with no clever encoding.

Would somebody be able to explain this paragraph or point me to some references that elaborates it better?

Answer 1

If we allow numbers to be unbounded while keeping the unit cost model (each operation costs one unit), we get a very powerful machine. For example, here is how to solve 3SAT in this model. Recall that a 3CNF is a formula of the form

$$ (x_1 \lor \lnot x_2 \lor x_3) \land (x_1 \lor x_4 \lor \lnot x_5) \land \cdots. $$

Here $\lor$ is logical OR, $\land$ is logical AND, and $\lnot$ is logical NOT. The 3CNF is an AND of clauses, each of which is the OR of three literals; a literal is either a variable or its negation. The 3SAT problem asks whether a given 3CNF is satisfiable, that is, whether there is a truth assignment to the variables under which the formula evaluates to TRUE.

Suppose the given 3CNF has $n$ variables. For a formula $\varphi$, let $T(\varphi)$ be a "bit-vector" of length $2^n$, indexed by truth assignments to the variables, such that the bit at position $x$ is the truth value of $\varphi$ evaluated at the assignment $x$ (i.e. 1 if $\varphi$ is TRUE and 0 if $\varphi$ is FALSE). We order the truth assignments in lexicographic order; for example, if $n=2$ then the truth assignments are $(F,F),(F,T),(T,F),(T,T)$, given in the format $(x_2,x_1)$. Continuing the example, $T(x_1) = 1010$ and $T(x_2) = 1100$ (we read the bits from right to left), both in binary notation.

Consider now the following operations:

1. For each $i$, we can compute $T(x_i)$ as follows: $$ \begin{align*} T(x_i) &= \sum_{a=0}^{2^{i-1}-1} \sum_{b=0}^{2^{n-i}-1} 2^{2^i b + 2^{i-1} + a} \\ &= 2^{2^{i-1}} \sum_{a=0}^{2^{i-1}-1} 2^a \sum_{b=0}^{2^{n-i}-1} (2^{2^i})^b \\ &= 2^{2^{i-1}} (2^{2^{i-1}}-1) \frac{(2^{2^i})^{2^{n-i}}-1}{2^{2^i}-1} \\ &= \frac{2^{2^{i-1}} (2^{2^{i-1}}-1)(2^{2^n}-1)}{2^{2^i}-1}. \end{align*} $$
2. Given $T(\alpha),T(\beta)$, we can compute $T(\lnot \alpha), T(\alpha\land\beta), T(\alpha\lor\beta)$ using bitwise NOT, AND, OR.

In this way, we can efficiently compute $T(\varphi)$, where $\varphi$ is the given 3CNF. The formula $\varphi$ is satisfiable iff $T(\varphi) \neq 0$. This gives a polynomial time algorithm for 3SAT in the unit cost model. Obviously something is wrong and needs fixing, which is what Tarjan is getting at.

Answer 2

This is a way to say that the complexity analysis will break down if assuming that a RAM machine can handle numbers of arbitrary length as 1 unit (think of a quantum computer which can solve np-complete problems using the superposition principle, what the author states as doing parallel computations on multiple numbers encoded as 1 unit). So the author states that the RAM machine does not handle arbitraty numbers but only those of certain length (the O(logN) cost).

UPDATE:

In a paper by Hartmanis and Simon on the power of multiplication in RAM machines (circa 1974), a result is derived where if a RAM machine can handle multiple opertions in parallel (or as one unit), then it is equivalent to a Non-deterministic Tuing machine, thus can solve NP-complete problems (in polynomial time). This is related to this question

Answer 3

You may be distracted by purely theoretical appproach of explanation.

This is a proof that you can implement every algorithm with integer numbers stored in RAM without asymptotic distortions. I mean $O(N)$ will be $O(N)$ on your computer.

It's true because every operation on integer number of limited (constant) size is $O(1)$. He say $n^c, c-small$ instead of $1$ just to show that, for example 32-bit type is the same as 64-bit type, and it's size do not change algorithm asymptotic (but it works slower on some part of computers, just because of resulting constant values defference).

I think author will give a proof for real numbers on next pages (by induction from integers), or even more - for every possible data type with "no clever encoding" (:D, but it really make sense).