Abstract

We introduce a new logical operator CSTC and show that incorporating this operator into first-order logic enables as to capture the complexity class PSPACE. We also show that by varying how the operator is applied we can capture the complexity classes P, NP, the classes of the Polynomial Hierarchy PH, and PSPACE. As such, the operator CSTC can be regarded as a general purpose operator. We also give applications of these characterizations by showing that P and NP coincide with those problems accepted by two new classes of program schemes , by producing some new complete problems for various complexity classes where the reductions are from first principles and do not use known complete problems , and by giving a simple proof that first-order logic incorporated with the least fixed point operator captures P