Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation? Let's say I had an optimization problem

$$ \min_{x \in D} f(x) $$

Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.

Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^*$ using finite numbers $LBD$ and $UBD$ where $LBD &lt; f^* \leq UBD$. 

Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon &gt; 0$ finds a real number $z$ such that $f^* \leq z \leq f^* + \epsilon$. 

For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them.
The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.

I'm handwaving a lot, because parametric search is quite complicated. This survey talks about ways of making it practical, and also has a decent explanation of the basic idea. This older survey gives a number of examples of parametric search.