The order maintenance problem (or "maintaining order in a list") is to support the operations:
singleton: creates a list with one item, returns a pointer to it
insertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
delete: given a pointer to an item, removes it from its list
minPointer: given two pointers to items in the same list, returns the one closer to the front of the list
I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.
- Athanasios K. Tsakalidis: Maintaining order in a generalized linked list
- Dietz, P., D. Sleator, Two algorithms for maintaining order in a list
- Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”
Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?