Complexity of logical theories involving coprimality

DOI10.1016/0304-3975(92)90250-JzbMath0772.03019MaRDI QIDQ1202924

Pascal Michel

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitylogical theoriescoprimality

Mathematics Subject Classification ID

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

Related Items

Computational complexity of logical theories of one successor and another unary function ⋮ A list of arithmetical structures complete with respect to the first-order definability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• A uniform method for proving lower bounds on the computational complexity of logical theories
• On the computational complexity of the theory of Abelian groups
• Complexity of Boolean algebras
• The complexity of logical theories
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• The computational complexity of logical theories
• Model theory
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Alternation
• On the complexity of the theories of weak direct powers
• Definability and decision problems in arithmetic
• On direct products of theories

This page was built for publication: Complexity of logical theories involving coprimality