Syntactic characterizations of completeness using duals and operators

摘要

This article extends the work laid down by Medina and Immerman for the syntactic characterization of complete problems via first-order projections. Our first contribution is a general canonical form for the sentences that characterize complete problems. This canonical form works for a wide collection of complexity classes, including L, NL, P, NP and PSPACE, which can be given in terms of any complete problem in the class and generalizes the canonical form for NP given by Medina and Immerman. Our second contribution is the definition of a new class of syntactic operators that can be used to show the completeness of a problem by purely syntactic means. We prove basic properties of the operators including the fact that any complete problem can be shown to be complete using such operators. The practical relevance of the operators is illustrated in a number of applications which includes new completeness results, and also the application of operators at problems at the second level of the polynomial-time hierarchy. In both contributions, duals of first-order projections play a major role. Thus, our results show that such duals are in fact very powerful syntactic tools in the field.