Recognition complexity of theories and their computational expressivity

DOI10.1007/S10469-012-9178-5MaRDI QIDQ694245zbMATH OpenOpenAlexFDO

Authors I. V. Latkin

Publication date 11 December 2012

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10469-012-9178-5

zbMATH Keywords

Boolean algebrascomputational complexity of a theorycomputational expressivity of a theoryundecidable theories

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)

Review text

The computational complexity of a first-order theory is the difficulty to prove or disprove a formal statement to be true in a given theory. There are decidable theories known to have computational complexities bigger than functions given by towers of exponents. The computational complexity for arbitrary theories of Boolean algebras is discussed. In parallel, a new notion is introduced: computational expressivity. This is the possibility of a theory to simulate long computations, and is a notion that can be applied also for undecidable theories. It is proven that Peano arithmetic has a computational expressivity bigger than Boolean algebras.

Recommendations

• The recognition complexity of decidable theories
• scientific article; zbMATH DE number 2203952
• scientific article; zbMATH DE number 2157312
• scientific article; zbMATH DE number 3979054
• Physical computational complexity and first-order logic

Cited in

(6)

• scientific article; zbMATH DE number 4028940 (Why is no real title available?)
• SOME RAMSEY THEORY IN BOOLEAN ALGEBRA FOR COMPLEXITY CLASSES
• scientific article; zbMATH DE number 2157312 (Why is no real title available?)
• The recognition complexity of decidable theories
• scientific article; zbMATH DE number 2203952 (Why is no real title available?)
• A remark on a paper of I. V. Latkin

This page was built for publication: Recognition complexity of theories and their computational expressivity

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