scientific article; zbMATH DE number 4200184

MaRDI QIDQ3348901zbMATH OpenFDO

Authors Erich Grädel

Publication date 1989

zbMATH Keywords

classification of the prefix vocabulary classes in P and in NPcomplexity of deciding satisfiability of formulas in full first order logic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Satisfiability of formulae with one \(\forall\) is decidable in exponential time
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• scientific article; zbMATH DE number 52574
• scientific article; zbMATH DE number 4116512
• scientific article; zbMATH DE number 4029504

Cited in

(8)

• scientific article; zbMATH DE number 4029504 (Why is no real title available?)
• Circuit complexity and the expressive power of generalized first-order formulas
• scientific article; zbMATH DE number 52574 (Why is no real title available?)
• First-Order Formulas in Conjunctive Quantificational Form
• Satisfiability of formulae with one \(\forall\) is decidable in exponential time
• Mechanizing Mathematical Reasoning
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• The complexity of definability by open first-order formulas

This page was built for publication:

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