RE: Let's not BE NP-hard, shall we...?
It looks like we are in complete agreement.
> ________________________________________
> From: Ralph Baker Kearfott [rbk@xxxxxxxxxxxx]
> The question here, however, is the relevance of this to our deliberations. In particular,
> "equivalent transformations," if I understand your idea correctly, deal with rearranging
> expressions according to the usual rules for real-valued expressions.
Correct.
> On the other hand,
> isn't the potential determinism we are considering here dealing with the result of a single
> unary or binary operation (i.e. one of the four elementary operations, a list of designated
> standard functions, or basic interval set operations such as union or intersection)?
> Isn't determinism as the result of rearrangement of expressions best left to people
> (or standardization committees) dealing with compilers? Given a particular order in which
> operations are done, the results of the operations (and corresponding decorations) can
> be well-defined.
I agree with you, but the general idea of determinism as discussed in several emails is that for every program (not just for the operation), the result should be the same, no matter where we implement it, no matter what optimizing transformations a specific compiler does, be it re-ordering -- or more serious transformations that are allowed by programming languages since they do not change the result of point-value computations.
Previous counter-arguments (e.g., by Arnold) were that determinism is now happening in usual computations anyway: since we have parallelism, the order of operations change unpredictably and thus, we cannot expect determinism unless we completely disallow parallelization and make computations much slower.
Some folks argued that with interval computations, the results are worse: standard complier tricks that lead to exact same results for point-wise computations, like reducing x-x to 0 or 2x-x to x, will change the result of straighforward interval computations.
My email posting was aimed at strenthening this argument:
that this same phenomenon will occur whether we use straightforward interval computations or whether we use any other feasible technique for computing an enclosure for the range.
Thus, full determinism on the level of a program as a whole is not attainable.