Let's not BE NP-hard, shall we...?
> From: "Kreinovich, Vladik" <vladik@xxxxxxxx>
> To: "N.M. Maclaren" <nmm1@xxxxxxxxx>, Dan Zuras Intervals
> <intervals08@xxxxxxxxxxxxxx>
> CC: "stds-1788@xxxxxxxxxxxxxxxxx" <stds-1788@xxxxxxxxxxxxxxxxx>
> Date: Thu, 4 Aug 2011 06:39:23 -0600
> Subject: RE: Determinism is hard & not the only thing on our plate...
>
> In general, the problem of providing form-invariant enclosure is NP-hard,
> see our paper
>
> http://www.cs.utep.edu/vladik/2011/tr11-35.pdf
>
> that we submitted recently to Reliable Computing
>
I am aware of this sort of thing & it is not what I
suggest.
Really, if the best possible enclosure is infeasible
we can have very little in the way of shalls to say
about it.
What I am suggesting that there is one known-in-advance-
&-predictable order of evaluation. It is the one that
is written into the source. It is THIS one that is
reliably & efficiently computable, albeit with a big
hit in parallelism.
Most languages have either a specified or implied
order of evaluation. That's the one that's predictable.
I am aware that Fortran specifies that the order of
evaluation is effectively NOT specified. I am also
aware that, while it IS specified in C, it is also
routinely ignored.
We can handle the other languages but those may be a
problem.
I don't know the solution. Perhaps the language
committees will accept that there must be a specified
& obeyed order of evaluation for INTERVAL expressions.
Perhaps not. I know some of these guys but I haven't
discussed it with them. Perhaps some of you can ask
them for us.
There are feasible ways to tackle this problem.
Let's not argue about the infeasible ones.
Dan