[ Is it normal that I don't see Ralf's messages? ]
"Bill Page" <[EMAIL PROTECTED]> writes: [...] | So is computational complexity a relative thing, i.e. we take | the operations from the representation as units and then express | the complexity of the operations of the new domain in terms of | these? Or is it an absolute thing that must be expressed in | terms of the most primitive domain (Lisp) or even deeper in | terms of a given hardware architecture? relative. | > After all that is a distincion between classic mathematics | > and constructive mathematics. | > | | I am not sure that I would agree that this is the right distinction. | Ultimately in computer algebra systems I think all mathematics must | be constructive. In a sense, that is what we mean by "algebra". An | existence proof or a proof by contradiction is not of much use in | such a system. | | > Example. You want to implement quicksort. Would someone choose | > lists to do that instead of arrays? | | In Axiom this is not really an appropriate question. quicksort | would be implemented in a generic manner so that it can be applied | to any domain that provides the necessary methods. In fact in the | Axiom book contains exactly this example (bubble sort actually). However, to call it quicksort, you have to meet some algorithmic complexity guarantee. | > Both basically represent the mathematical idea of tuples. | | No, I don't think so. As mathematical objects lists, arrays and | tuples are all quite distinct however I agree that they all provide | the necessary methods on which sort may operate. The notion of sorting is defined terms of order and permutation. [...] | > > For example, is an Axiom set, i.e. a member of the domain Set, | > > a data structure or a mathematical structure? | > | > How expensive is it to add a new element to an existing set of | > type Set(T) where T has no ordering function? How expensive is | > it to add a new element to Set(T) if T provides an ordering | > function? | > | | All domains that have SetCategory are required to have a hash into | SmallInteger. That is not a mathematical requirement. | I suppose that this means that the cost of adding | new elements is independent of Type T. Why? _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
