Descriptive characterizations of computational complexity

摘要

Elementary computations over relational structures give rise to computable relations definable by formulas of the form (∀ relations) (∃ objects) ϕ with ϕ quantifier free. Particular complexity classes, such as NLog-Space, P-Time, P-Space and Exp-Time, can each be characterized by a particular variant of the computation model, and the computable relations of each such variant are precisely the ones defined by certain syntactic variants of formulas of the form above. Thus a descriptive characterization in higher order logic is obtained for each such complexity class. Several known descriptive characterizations of complexity classes ensue.