A generalization of Fagin´s theorem

Fagin´s theorem characterizes NP as the set of decision problems that are expressible as second-order existential sentences, i.e., in the form (∃Π)φ, where Π is a new predicate symbol, and φ is first-order. In the presence of a successor relation, φ may be assumed to be universal, i.e., φ≡(∀x¯)α where α is quantifier-free. The PCP theorem characterizes NP as the set of problems that may be proved in a way that can be checked by probabilistic verifiers using O(log n) random bits and reading O(1) bits of the proof: NP=PCP[log n, 1]. Combining these theorems, we show that every problem D∈NP may be transformed in polynomial time to an algebraic version Dˆ∈NP such that Dˆ consists of the set of structures satisfying a second-order existential formula of the form (∃Π)(R˜x¯)α where R˜ is a majority quantifier-the dual of the R quantifier in the definition of RP-and α is quantifier-free. This is a generalization of Fagin´s theorem and is equivalent to the PCP theorem