On the Complexity of Recurrence Evaluation
The paper provides complexity-theoretic lower bounds for recurrence evaluation problems, which are fundamental in areas like game theory and dynamic programming.
The paper studies the computational complexity of evaluating finitely valued recurrent functions, showing that the recurrence problem for sequences is PSPACE-complete or EXP-complete depending on offset representation, and that evaluating recurrences defined by NAND (related to impartial games) is PP-hard even for a simple 3D game.
In this paper, we study the complexity of the recurrence evaluation problem. We are interested in finitely valued recurrent functions. We present two results in this direction. First, we study the recurrence problem for sequences, assuming that a recurrence relation is defined by a fixed function, while the offsets are part of the input. Depending on the form of presentation (whether the offsets are given in unary or in binary), the problem is PSPACE-complete or EXP-complete. Second, we study recurrences defined by the NAND function. They are related to impartial games. We prove PP-hardness of the recurrence evaluation problem for a very simple 3-dimensional game, in which the offset vectors are coordinate vectors (1,0,0), (0,1,0) and (0,0,1) but the boundary conditions are arbitrary. In other words, we consider generalized winning conditions for the game extending the normal and the misère winning conditions.