Dyn-FO (preliminary version): a parallel, dynamic complexity class
Sushant Patnaik, Neil Immerman · 1994
Traditionally, computational complexity has considered only static problems. Classical Complexity Classes such as NC, P, NP, and PSPACE are defined in terms of the complexity of checking—upon presentation of an entire input—whether the input satisfies a certain property.