Positive First-Order Logic Is NP-Complete

DOI10.1147/RD.254.0327MaRDI QIDQ3937380zbMATH OpenOpenAlexFDO

Authors Dexter Kozen

Publication date 1981

Published in IBM Journal of Research and Development (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1147/rd.254.0327

zbMATH Keywords

positive first-order sentence

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cited in

(11)

• Fast algorithms for testing unsatisfiability of ground Horn clauses with equations
• Generators, indecomposables and free algebras
• Complete sets of transformations for general E-unification
• Decidability and complexity of simultaneous rigid E-unification with one variable and related results
• Logic with equality: Partisan corroboration and shifted pairing
• The ground-negative fragment of first-order logic is -complete
• The complexity of counting quantifiers on equality languages
• Simultaneous rigid E-unification is undecidable
• The undecidability of simultaneous rigid E-unification
• On polynomial-time decidability of k-negations fragments of first-order theories
• Rigid E-unification: NP-completeness and applications to equational matings

This page was built for publication: Positive First-Order Logic Is NP-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3937380)