Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Let's not BE NP-hard, shall we...?

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.  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.


Best regards,

Baker

On 8/5/2011 2:10 AM, Kreinovich, Vladik wrote:

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.




--

---------------------------------------------------------------
Ralph Baker Kearfott,   rbk@xxxxxxxxxxxxx   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------