**debray@sbcs.UUCP (Saumya Debray)** (12/24/83)

: Given two logics A and B, and A is more expressive than B: (1) if A and B are both decidable, does the fact that A is more expressive than B imply that A's decision procedure is harder (i.e. of higher complexity) than B's? (2) if A and B are not both decidable, does the fact that A is more expressive than B imply that A is of a higher unsolvability degree than B? -- Saumya Debray SUNY at Stony Brook {floyd, bunker, cbosgd, mcvax, cmcl2}!philabs! \ Usenet: sbcs!debray / {allegra, teklabs, hp-pcd, metheus}!ogcvax! CSNet: debray@suny-sbcs@CSNet-Relay

**condict@csd1.UUCP (Michael Condict)** (12/27/83)

Well, it's nice to finally see something other than number theory or real analysis mentioned in this group. I'm not sure of exactly what you mean by "logic" and by "A is more expressive than B" but under the most likely assumptions, question (1) can be answered as follows (the question was: when A is more expressive than B and both are decidable is it guaranteed that A's decision procedure is harder than B's): (i) By "logic", I assume you mean any formal language with a semantic definition that assigns truth values to strings (or sentences) in the language (and possibly an associated calculus for proving theorems) (ii) If by "more expressive" you mean that the language of A contains the language of B as a subset, then the answer is easy. Since each sentence of B is a sentence of A, A's decision procedure can be directly used for B, so it certainly cannot be any harder to decide truths in B. It may, however, be just as hard to decide B. (ii) Under the more general assumption that A expresses B under some translation (from sentences of B to sentences of A that are equivalent), then the immediate answer is that it can not be harder to decide B than the sum of the complexity for A and complexity of the translation. As usual, if the translation is polynomial, one can safely ignore it when dealing with complexity classes of polynomial degree or higher. (iii) I'm afraid, however, that you were really interested in the case when A can express B but B cannot express A (that is when A is strictly more expressive than B) and that you wanted to know whether that meant the decision procedure for A had to be strictly harder than for B. Well, to answer that, it must first be clear exactly what you mean by "B cannot express A", because if A and B are both decidable, and B can express both *true* and *false* then, in some sense, the computable function that takes any valid sentence of A to *true* in B and any invalid sentence to *false* correctly expresses A in B. However, if by "expresses" you mean that each sentence of A must be mapped to a sentence of B containing the same set of free variables and in such a way that, for every interpretation giving values to those free variables, the B sentence has the same truth value as the A sentence, then I don't know the answer. I believe the analysis for the undecidable case (question (2)) is similar. Michael Condict ...!cmcl2!csd1!condict Courant Inst., N.Y.U.