**Abstract:
**
Fagin's theorem characterizes NP as the set of decision problems that are
expressible as second-order existential sentences, i.e., in the form
(exists Pi)phi, where Pi is a new predicate symbol, and phi is first-order.
In the presence of a successor relation, phi may be assumed to be
universal, i.e., phi = (forall x)alpha where alpha 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 in NP may be transformed in
polynomial time to an algebraic version hat{D} in NP such that hat{D}
consists of the set of structures satisfying a second-order existential
formula of the form (exists Pi)(tilde{R} x)alpha where tilde{R} is a
majority quantifier -- the dual of the R quantifier in the definition of RP
-- and alpha is quantifier-free. This is a generalization of Fagin's
theorem and immediately implies the PCP theorem.

Recent Publications of Neil Immerman