[Ecls-list] Re: HEADS UP!

[Paul F. Dietz]

Juan Jose Garcia Ripoll wrote:

> The interesting thing about Baker's approach is that there is no scalability 
> problem. Performing a SUBTYPEP takes O(2N^2) operations, where N is the 
> number of elements in the type (and maybe pre-registered types).

Baker worked on his algorithm just before the CONS type specifier was
added.  With (CONS ... ...) types, a type specifier of size N can
specify a type with exponentially many (in N) elements.  For example:

   (CONS BIT (CONS BIT (CONS ... (CONS BIT NULL) )))

With n BITs, this specifies all proper lists of length n whose elements
are 0 or 1.

It's not hard to reduce the tautology problem on disjunctive normal
form boolean formulas to a subtypep query on cons types.  DNF tautology
is co-NP complete.

	Paul