IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 25, Number 4, Page 327 (1981)
Finite Element Analysis
  Full article: arrowPDF   arrowCopyright info


Positive First-Order Logic Is NP-Complete

by D. Kozen
The decision problem for positive first-order logic with equality is NP-complete. More generally, if Σ is a finite set of atomic sentences (i.e., atomic formulas of the form t1 = t2 or Rt1 ... tn containing no variables) and negations of atomic sentences and if ɸ is a positive first-order sentence, then the problem of determining whether ɸ is true in all models of Σ is NP-complete.
Related Subjects: Complexity; Mathematics (applied)