Positive First-Order Logic Is NP-Complete

DOI10.1147/rd.254.0327zbMath0481.03026OpenAlexW2062893737MaRDI QIDQ3937380

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)

Related Items (9)

Fast algorithms for testing unsatisfiability of ground Horn clauses with equations ⋮ Generators, indecomposables and free algebras ⋮ Rigid E-unification: NP-completeness and applications to equational matings ⋮ The undecidability of simultaneous rigid E-unification ⋮ The complexity of counting quantifiers on equality languages ⋮ The ground-negative fragment of first-order logic is -complete ⋮ 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

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