Paper: A generalization of Fagin's theorem (at LICS 1996)

Authors: J. Antonio Medina Neil Immerman

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 (/spl exist//spl Pi/)/spl phi/, where /spl Pi/ is a new predicate symbol, and /spl phi/ is first-order. In the presence of a successor relation, /spl phi/ may be assumed to be universal, i.e., /spl phi//spl equiv/(/spl forall/x~)/spl alpha/ where /spl 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/spl isin/NP may be transformed in polynomial time to an algebraic version D/spl circ//spl isin/NP such that D/spl circ/ consists of the set of structures satisfying a second-order existential formula of the form (/spl exist//spl Pi/)(R/spl tilde/x~)/spl alpha/ where R/spl tilde/ is a majority quantifier-the dual of the R quantifier in the definition of RP-and /spl alpha/ is quantifier-free. This is a generalization of Fagin's theorem and is equivalent to the PCP theorem.

BibTeX

  @InProceedings{MedinaImmerman-AgeneralizationofFa,
    author = 	 {J. Antonio Medina and Neil Immerman},
    title = 	 {A generalization of Fagin's theorem},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS 1996)},
    year =	 {1996},
    month =	 {July}, 
    pages =      {2--12},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }