Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: First Order Predicate Logic Without Negation is NP-Complete
Authors: Kozen, Dexter
Keywords: computer science
technical report
Issue Date: Apr-1977
Publisher: Cornell University
Abstract: Techniques developed in the study of the complexity of finitely presented algebras are used to show that the problem of deciding validity of positive sentences in the language of first order predicate logic with equality is $\leq_{\log}$-complete for NP.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
77-307.pdf751.29 kBAdobe PDFView/Open
77-307.ps394.45 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us