Accuracy-goal-driven interval-based computations: ``Evaluate this expression to a value with relative error less than R.'' Assume you can bump up the precision of all inputs, the expression is suitably continuous and differentiable, and you can implement all needed routines in interval arithmetic to arbitrary precision.
Try it with precision p. If you fail to meet the accuracy requirement, try precision 2*p. etc.
Mathematica seems to have some fuzzy claims about trying to do this for ``any'' evaluation;
Many library routines exist for targeted accuracy (say, for quadrature, zerofinding, etc).