Bounded memory computation

Bounded Memory Computation

“By far the most important and well studied space-bounded complexity class is L, consisting of problems solvable on O(log n) space. We list here a few basic problems in this class. The reader may want to find such small-space algorithms for them (most are quite simple).” [From Wigderson’s book, Chapter 14th]

• Arithmetic problems. Given two integers, compute their sum, product, and one modulo the other. • Comparison problems: Compare two integers, sort a set of integers. • 2-coloring. Given a graph, determine whether it is bipartite. • Word problem in the free group. [LZ77] Given a sequence from the alphabet {a, a−1, b, b−1}, determine whether their product is the identity.

Arithmetic Problems

Addition(A,B)

carry=0 for $i\leftarrow{1,..,n}$ $\space$output[i] = A[i]+B[i]+carry $\space$update carry. done.

Memory used - index $i$, up to $logn$ bits.