Languages that capture complexity classes. (English) Zbl 0634.68034

Immerman, Neil

SIAM J. Comput. 16, 760-778 (1987).

Some results on interrelations between the problems expressible by logical languages and the complexity classes are proved. The set \(1^{st}O\) of all finite models of the first order languages is strictly contained in the complexity class L (deterministic logspace). Adding the operator pos TC of the positive reflexive transitive closure of the relations, the author proves the coincidence \(NL=1^{st}O+pos TC\). Moreover \(L=1^{st}O+DTC\), where DTC is the deterministic version of the transitive closure. Similar results on the descriptions of the polynomially space complexity classes in the terms of second order logical languages are ascertained, in particular \(PSPACE=2^{nd}O+TC\).

Reviewer: D.Yu.Grigor’ev

MSC:

68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

bounded depth circuits; quantifier alternations; logical languages; transitive closure; complexity classes