Conditional and Unconditional Separations of Dynamic Complexity Classes

Dynamic computational complexity is the study of resource bounded dynamic computation. We study the computational power of a persistent data structure that processes a stream of updates and queries, using limited computational resources. In this paper, we define new, extremely restricted dynamic complexity classes. We show that these classes are strictly contained in previously studied dynamic complexity classes. We also prove some conditional separations: the strongest separation of dynamic complexity classes we prove depends on the conjecture that the static complexity classes L/poly and P/poly are not equal. Finally, we show that these extremely low dynamic complexity classes have surprising power. We show that the dynamic computation class DynProjections can compute any PSPACE problem, given exponential time.