On Oct 21, 2008, at 10:35 AM, Mitch Harris wrote: On Tue, Oct 21, 2008 at 10:11 AM, John F. Sowa < sowa@xxxxxxxxxxx> wrote: But the most misleading point of all is the final sentence:
Lastly, expressiveness increases the computational costs of reasoning.
In the Fads and Fallacies paper, I make the point that computational
complexity is *totally dependent* on the nature of the problem.
Any problem stated in a restricted language can be solved just as
fast when stated in a more expressive language.
I think there is a mismatch between how people are using implicit quantifiers here.
Indeed, and your analysis below is right on the money, with just one small caveat: you seem to identify being more expressive with having more operators. But there are other ways it can happen. Sometimes, a language may be made more expressive simply by removing syntactic restrictions. For example, the only syntactic difference between FOL and (some versions of) HOL is that the latter allows quantifiers to range over relation symbols, and provides some extra inference rules to establish the existence of relations. No extra operators at all. (Some versions of HOL do provide extra syntax, such as lambdaexpressions.)
The moral is that establishing more/less expressiveness isn't always as simple as counting operators; it can be a subtle and delicate matter. And, same point made differently, subtle changes in a KR language can have large effects on expressivity (and hence of inferential complexity).
True, for any particular problem, it is in a particular complexity class or not. Its complexity (computational) does not change.
But for given a set of language operators with specific meanings, the complexity of a the set of all problems expressible with larger selection of operators is at least as difficult (takes as long or longer) for a smaller set.
For a particular problem, if you know ahead of time which complexity class it lives in, you can gear the algorithm to that. But if you don't know that about the input, a simple problem may be expressed (equivalently of course) using the larger set of operators and you may still be bound by the algorithm needed to deal with the larger set to do all sorts of expensive, time consuming things.
Exactly. This is the key point that John seems to miss in his posts on this topic.
It should perhaps be stated for the benefit of forum readers, that this topic of inference complexity and the complexity/expressivity tradeoff is not at all new or speculative: it is a mature science now, with a fully workedout underlying theory, and is regularly applied in industrialscale applications, undergraduate textbooks, etc. etc.. True, it focuses on worstcase analysis, and 'averagecase' or 'typicalcase' results would be a lot more use in practice but are virtually unobtainable: still, many purely empirical studies of large sets of problems have shown again and again that there are real 'tradeoff cliffs' in practical problem sets which clearly partition the problem space into easy vs. nearworstcasehard (the latter usually in a 'boundary zone' between two 'easy' areas.) Citing stoneage results like Wang's theoremprover isn't relevant. That engine could not have even input the problems that get tackled these days: there wasn't enough RAM on the planet at that time. Some algorithms are 'adaptive' in that they are faster for simpler inputs(less expressive; using fewer of the fancy operators), but some algorithms are not, and no matter what the input (for a given size) it runs in the same time (e.g. tableau algorithms vs automata based ones for description logics). There is no guarantee that a set of problems has an adaptive algorithm.
Any problem can be solved as fast as it ..well... can be. But you don't know ahead of time which problem it is.
Of course, just syntax checking is an extremely effective triage method. But there's no guarantee (a simple statement can be expressed badly, with lots of annoying highcomplexity operators). Increasing expressiveness increases the complexity of solving the whole class.
So, yes, for a specific problem, stated in a particular manner, of course adding operators to the language it is expressed in doesn't change the complexity of the original problem. But equally of course the extra operators make more problems expressible and they might take longer, and if you don't realize it, you may spend more time than necessary on the simpler problem (that doesn't actually use those new operators).
Does that clarify how I think people are talking about 'expressiveness'
Yup.
Pat
 IHMC (850)434 8903 or (650)494 3973 40 South Alcaniz St. (850)202 4416 office Pensacola (850)202 4440 fax FL 32502 (850)291 0667 mobile
