Characterization of Complexity Classes in Higher-Order Logic
Daniel M. Leivant · 1987
We show, for a number of computational complexity classes, that the problems therein are precisely the problems explicitly definable by those formulas of higher order logic that obey a certain syntactic constraint. The complexity classes thus characterized include NLog.space, Ptime, NPtime (Fagin's Theorem), Ptimellicrarchy, Exp.time, NExp.time, ExpHicrarchy, ExpSpace, and DoublyExp.time.