# complexity theory – NP-hardness proof of an optimization problem with real values and real input in the decision problem

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:

1. $$I_{mathcal{P}}$$ is the set of instances of $$mathcal{P}$$;
2. $${SOL}_{mathcal{P}}$$ is a function that associates to any input instance $$x in I_{mathcal{P}}$$ the set of feasible solutions of $$x$$;
3. $$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$$;
4. $${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.

Posted on Categories Articles