Generic complexity of first-order theories

MaRDI QIDQ890867zbMATHFDO

Authors Alexander Rybalov

Publication date 16 November 2015

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL http://semr.math.nsc.ru/v8/p168-178.pdf

zbMATH Keywords

first-order theorygeneric complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Generic undecidability of universal theories
• Generic complexity of Presburger arithmetic
• Generic Complexity of Presburger Arithmetic
• On generic complexity of the existential theories
• On generic complexity of the validity problem for Boolean formulas

Cited in

(13)

• The Complexity of Decomposing Modal and First-Order Theories
• On the generic existential theory of finite graphs
• On generic complexity of the existential theories
• Generic Complexity of Presburger Arithmetic
• The Exact Complexity of the First-Order Logic Definability Problem
• Dynamic notions of genericity and array noncomputability
• Inductive Logic Programming
• scientific article; zbMATH DE number 7333179 (Why is no real title available?)
• Generic complexity of Presburger arithmetic
• Generic undecidability of universal theories
• The complexity of definability by open first-order formulas
• scientific article; zbMATH DE number 2222019 (Why is no real title available?)
• Circuit complexity and the expressive power of generalized first-order formulas

This page was built for publication: Generic complexity of first-order theories

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