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