On Tue, Oct 21, 2008 at 10:11 AM, John F. Sowa <sowa@xxxxxxxxxxx> wrote: (01)
> 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. (02)
I think there is a mismatch between how people are using implicit
quantifiers here. (03)
True, for any particular problem, it is in a particular complexity
class or not. Its complexity (computational) does not change. (04)
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. (05)
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. (06)
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. (07)
Any problem -can- be solved as fast as it ..well... can be. But you
don't know ahead of time which problem it is. (08)
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 high-complexity operators). Increasing
expressiveness increases the complexity of solving the whole class. (09)
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). (010)
Does that clarify how I think people are talking about
'expressiveness' or does it make it worse? (011)
Mitch (012)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (013)
|