[32] Consider a singly linked list L of n items, where the ith item has a pointer pointing to the (i + 1)st item, with the last pointer being nil. Let  > 0, prove:

(a) Every sequence of t(n) ≥ n steps of going backward on L can be done in O(t(n)n) steps, without modifying L or using extra memory other than O(1) extra pointers or counters.

(b) Any program using O(t(n)n) steps to go back t(n) steps on L requires at least k − 1 pointers.

Comments. Hint: Item

(a) does not need Kolmogorov complexity. You can use O(n) initial start time. For Item (b), if a region passed by does not get visited by a pointer during this process, then it can be compressed. Source: [A.M. Ben-Amram and H. Petersen, Proc. 31st ACM Symp. Theory Comput., pp. 780–786, 1999].