Re: [CL] Re: Decidability
Pat, Chris, Michael, et al.,
I agree with Pat that decidability tells us only that
a particular problem is solvable in a finite amount
of time, but since it sets no limit on that amount,
it is of much less value than giving us a better
upper bound, such as exponential, polynomial, linear,
or logarithmic.
The attached diagram, complex.gif, illustrates the
issues by showing a range of complexity classes as
a function of the number N of items involved:
1. The upper bound is infinity for truly undecidable
problems that cause the computer to loop forever.
Knowing that a problem is decidable tells us only
that it takes something less than infinity.
2. Exponential time is usually considered bad, but
for small values of N (around 10 or less), it
might not be bad. For N=100 or more, it is
disastrous.
3. Polynomial time is often considered *tractable*
or good, but for N of the size of the web (several
billion pages and counting), N-squared time can
be thousands or millions of years.
4. (N log N) is proportional to the time a good
algorithm requires to sort N items. Algorithms
of this complexity or less are *scalable* since
they can be applied to the web and other large
collections of data with current technology.
5. The ideal is constant-time algorithms, which are
independent of the size of the data. Hash coding
can come close to this limit, but the time to build
the hash tables for N items tends to be (N log N).
Bottom line: Complexity issues are very important, but
decidability is an insignificant aspect of complexity
when we are concerned with data of the size of the web.
John
