Characterization of Complexity Classes in Higher-Order Logic
- 1 June 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: