Publication:3949037
From MaRDI portal
zbMath0488.03021MaRDI QIDQ3949037
Publication date: 1981
upper bound; divisibility; space complexity; decision procedure; deterministic Turing machine; theory of natural numbers
03B25: Decidability of theories and sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
03D10: Turing machines and related notions
03F20: Complexity of proofs
Related Items
A list of arithmetical structures complete with respect to the first-order definability, Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, Complexity of logical theories involving coprimality, On the complexity of decision using destinies in \(H\)-bounded structures