Languages that capture complexity classes. (English) Zbl 0634.68034

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


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI Link