Re: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory)

[Gabriel Dos Reis]

[ Is it normal that I don't see Ralf's messages? ]


"Bill Page" <address@hidden> 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?