Languages that Capture Complexity Classes

We present a series of operators of apparently increasing power which when added to first-order logic produce a series of languages in which exactly the properties checkable in a certain complexity class may be expressed. We thus give alternate characterizations of most important complexity classes. We also introduce reductions appropriate for our setting: first-order translations, and a restricted, quantifier free version of these called projection translations. We show that projection translations are a uniform version of Valiant’s projections, and that the usual complete problems remain complete via these very restrictive reductions.