number encoding effect on complexity
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:


For each $i$, we can compute $T(x_i)$ as follows:
$$
\begin{align*}
T(x_i) &amp;= \sum_{a=0}^{2^{i-1}-1} \sum_{b=0}^{2^{n-i}-1} 2^{2^i b + 2^{i-1} + a} \\ &amp;= 2^{2^{i-1}} \sum_{a=0}^{2^{i-1}-1} 2^a \sum_{b=0}^{2^{n-i}-1} (2^{2^i})^b \\ &amp;=
2^{2^{i-1}} (2^{2^{i-1}}-1) \frac{(2^{2^i})^{2^{n-i}}-1}{2^{2^i}-1} \\ &amp;=
\frac{2^{2^{i-1}} (2^{2^{i-1}}-1)(2^{2^n}-1)}{2^{2^i}-1}.
\end{align*}
$$
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.