Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7017
 Title: First Order Predicate Logic Without Negation is NP-Complete Authors: Kozen, Dexter Keywords: computer sciencetechnical report Issue Date: Apr-1977 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-307 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. URI: http://hdl.handle.net/1813/7017 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat