Paper: A syntactic characterization of NP-completeness (at LICS 1994)

Authors: J. Antonio Medina Neil Immerman

Abstract

Fagin (1974) proved that NP is equal to the set of problems expressible in second-order existential logic (SO∃). We consider problems that are NP-complete via first-order projections (fops). These low-level reductions are known to have nice properties, including the fact that every pair of problems that are NP-complete via fops are isomorphic via a first-order definable isomorphism (E. Allender et al., 1993). However, before this paper, fewer than five natural problems had actually been shown to be NP-complete via fops. We give a necessary and sufficient syntactic condition for an SO∃ formula to represent a problem that is NP-complete via fops. Using this condition we prove syntactically that 29 natural NP-complete problems remain complete via fops

BibTeX

  @InProceedings{MedinaImmerman-Asyntacticcharacter,
    author = 	 {J. Antonio Medina and Neil Immerman},
    title = 	 {A syntactic characterization of NP-completeness},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS 1994)},
    year =	 {1994},
    month =	 {July}, 
    pages =      {241--250},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}
  }