**Question** – Let’s suppose we have an optimization problem $mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $mathcal{P}_D$ (please see definitions below). Let’s say we have a reduction from an $NP$-complete problem to a decision problem $mathcal{P}_D’$ with $W in mathbb{R}$, where $W$ is of the form $f(w^p), w in mathbb{Q}, p in mathbb{R}$ fixed, and $f(.)$ is a simple algebraic function. Finally, let’s say $mathcal{P}_D$ contains $mathcal{P}_D’$. Can we conclude an $NP$-hardness result for $mathcal{P}$ here in any way?

I’ve found this NP-hardness of an optimization problem with real value related question. In case of $mathcal{P}_D’$ and for a fixed $p$ the value of $W$ comes from a countable set so I think the $NP$-hardness follows but I’m not sure I understood everything correctly.

Also, Manyem (2013) uses an $NP$-optimization problem definition, where the measure function takes values in $mathbb{R}_0^{+}$. He notes that “when it comes to computer representation, rational numbers will be used”. At the same time he defines the decision version of the optimization problem, which also uses a constant $W in mathbb{R}_0^{+}.$ So I wonder whether a precise argument for $NP$-hardness could be made using this computer representation too. Any reference is much appreciated.

— Key definitions from Ausiello et al. (2003) —

**Definition 1** – An optimization problem $mathcal{P}$ is characterized by the following quadruple of objects $(I_{mathcal{P}}, {SOL}_{mathcal{P}}, m_{mathcal{P}}, {goal}_{mathcal{P}})$, where:

- $I_{mathcal{P}}$ is the set of instances of $mathcal{P}$;
- ${SOL}_{mathcal{P}}$ is a function that associates to any input instance $x in I_{mathcal{P}}$ the set of feasible solutions of $x$;
- $m_{mathcal{P}}$ is the measure function, defined for pairs $(x,y)$ such that $x in I_{mathcal{P}}$ and $y in {SOL}_{mathcal{P}}(x)$. For every such pair $(x,y)$, $m_{mathcal{P}}$ provides a positive integer which is the value of the feasible solution $y$;
- ${goal}_{mathcal{P}} in { min, max }$ specifies whether $mathcal{P}$ is a maximization or a minimization problem.

Ausiello et al. (2003) makes a note at point 3 that in practice for several problems the measure function is defined to have values in $mathbb{Q}$, and that it is equivalent with the above one.

Denote the value of an optimal solution of $x$ by $m^{*}(x)$. Then the corresponding decision problem to $mathcal{P}$ is the following:

**Decision Problem** ($mathcal{P}_D$) – Given an instance $x in I$ and a positive integer $W in mathbb{Z}^{+}$, decide whether $m^{*}(x) geq W$ (if goal $= max$) or whether $m^{*}(x) leq W$ (if goal $= min$). If goal $= max$, the set ${ (x,W) | x

in I wedge m^{*}(x) geq W }$ (or ${ (x,W) | x

in I wedge m^{*}(x) leq W }$ if goal $= min$) is called the *underlying language* of $mathcal{P}$.

Based on the above note I assume when the measure function is defined to have values in $mathbb{Q}$ then the variable $W$ may also have values in $mathbb{Q}$ in the above definition.

**Definition 2** – An optimization problem $mathcal{P}$ is called $NP$-hard if, for every decision problem $mathcal{P}’ in NP, mathcal{P}’ leq_{T}^{p} mathcal{P}$, that is, $mathcal{P}’$ can be solved in polynomial time by an algorithm which uses an oracle that, for any instance $x in I_{mathcal{P}}$, returns an optimal solution $y^{*}(x)$ of $x$ along with its value $m^{*}_{mathcal{P}} (x)$.

References:

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A. and Protasi, M. (2003). Complexity and approximation: Combinatorial optimization problems andtheir approximability properties. Springer-Verlag Berlin Heidelberg 1999. DOI: 10.1007/978-3-642-58412-1.

Manyem, P. (2013). Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap. A Journal of Mathematical Programming and Operations Research. 62(9):1227-1246. DOI: 10.1080/02331934.2011.625027.