RE: Let's not BE NP-hard, shall we...?
Just a minor clarification: the paper I cited is NOT about the known result (proven in the 1970s) that computing the best possible enclosure (i.e., the actual range of the function) is NP-hard.
What I am citing is a new result which is exactly about determinism.
Basically, what we prove in this paper is that it is NOT possible to have a feasible interval enclosure algorithm which is independent on the equivalent transformations of the original expression. So, no matter what feasible method we produce, there exist an example of two equivalent expressions for which this method produces DIFFERENT results.
In other words, even if we are not aiming for the BEST possible results, even if we are happy to have cruder results, full absolute determinism of intereval computations (when the result is the same after any equivalent transformation) is simply not feasibly possible.
________________________________________
From: ben@xxxxxxxxx [ben@xxxxxxxxx] On Behalf Of Dan Zuras Intervals [intervals08@xxxxxxxxxxxxxx]
Sent: Thursday, August 04, 2011 7:46 AM
To: Kreinovich, Vladik
Cc: stds-1788@xxxxxxxxxxxxxxxxx; Dan Zuras Intervals
Subject: 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.