An information-theoretic approach to time bounds for on-line computation

摘要

Static, descriptional complexity (program size) can be used to obtain lower bounds on dynamic, computational complexity (such as running time). We discuss the approach and use it to obtain lower time bounds for on-line simulation of one abstract storage unit by another. Our main results show that more points of access into multidimensional or tree-shaped storage can save significant time.