Computational aspects of arity hierarchies. (English) Zbl 0894.03019

Dalen, Dirk van (ed.) et al., Computer science logic. 10th international workshop, CSL ’96. Annual conference of the EACSL, Utrecht, the Netherlands. September 21–27, 1996. Selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 1258, 211-225 (1997).
To some important complexity classes, \(\mathcal K\), there correspond logics, \(\mathcal L\), in the sense that the queries definable in \(\mathcal L\) are exactly those computable in \(\mathcal K\). [See e.g. N. Immerman, “Languages that capture complexity classes”, SIAM J. Comput. 16, 760-778 (1987; Zbl 0634.68034).] For example, second-order logic (SO) is known to correspond to the class PH. The paper under review considers hierarchies obtained within the known logics such as SO, LFP (least fixed point logic), and PFP (partial fixed point logic) by restricting from above the arities of second order variables allowed in logical formulas. In the case of PFP logic, the hierarchy is shown to correspond precisely to the degree of polynomial space (PSPACE) complexity levels. Even though the logics LFP and SO are known to capture the complexity classes PTIME and PH respectively, the author comes to the conclusion that the arity hierarchies of those two logics do not have straightforward complexity counterparts. It is shown nevertheless that some long-standing problems in complexity theory are equivalent to whether or not the arity hierarchies introduced in this work collapse.
For the entire collection see [Zbl 0868.00033].


03D15 Complexity of computation (including implicit computational complexity)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)


Zbl 0634.68034