I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated.

For the question, take the balanced MSSC problem as an example:

Balanced MSSC ($\mathcal{P}$) - Given a set of $n$ points $X=\{x_1, \dots, x_n \} \subset \mathbb{R}^n$ find a partition $\mathcal{C} = \{ C_1, \dots, C_K \}$ of $K$ clusters with equal cardinalities which minimizes $\sum_{k=1}^K \sum_{i: x_i \in C_k} \| x_i - c_k \|^2$, where $c_k$ is the centroid of the points $x_i \in C_k$.

Pyatkin et al. (2017) prooves the $NP$-hardness (please see definitions below) of this optimization problem for $n/K=3$. For this, they use a polynomial-time reduction from the Partition into Triangles (PiT) $NP$-complete problem to a decision problem $\mathcal{P}_D$ which is restricted to vectors $x_i \in \{0,1\}^q$. They proove that solving PiT is equivalent to finding a partition in problem $\mathcal{P}_D$ for which the value of the measure function ($m_{\mathcal{P}}$) is smaller than or equal to some $W \in \mathbb{Q}$. According to my understanding $NP$-hardness result follows because in this way we could use the optimization problem as an oracle to solve the PiT problem.

Question - Definition 1 does not include optimization problems with measure functions with real values. I assume the definition 'naturally' extends to this case and the above approach can be used because $W \in \mathbb{Q}$ in $\mathcal{P}_D$, and the oracle is assumed to do the calculation in one step no matter if the measure function is real- or rational-valued. Is it correct?

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


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.

Pyatkin, A., Aloise, D. and Mladenović, N. (2017). NP-hardness of balanced minimum sum-of-squares clustering. Pattern Recognition Letters, 97:44–45. DOI: 10.1016/j.patrec.2017.05.033.

  • $\begingroup$ Thanks for your detailed question! With our site format, we want posts here to ask only one question per post. It looks like you have three questions. These can be asked separately, in three separate posts. $\endgroup$
    – D.W.
    Sep 5, 2021 at 22:56
  • $\begingroup$ @D.W. Sorry about that. I'm creating separate posts for the questions. $\endgroup$ Sep 5, 2021 at 23:24
  • $\begingroup$ The Balanced MSSC ($\mathcal{P}$) defined above is for real-valued inputs and measure function. And, the NP-hardness proof given by Pyatkin is for rational-valued inputs and measure function. Then, the NP-hardness does follow for real-valued inputs and measure function. What is the problem? $\endgroup$ Sep 6, 2021 at 10:39
  • $\begingroup$ Are you asking if the definition of Balanced MSSC ($\mathcal{P}$) fits Definition $1$? That is, is it right to call the Balanced MSSC problem an optimization problem? $\endgroup$ Sep 6, 2021 at 10:40
  • 1
    $\begingroup$ @InuyashaYagami My explicit question is more like the 'why'. I mean what is the exact logical reasoning to say that $\mathcal{P}$ is $NP$-hard based on the reduction to the rational-valued decision problem? I think real-valued optimization problems don't fit Definition 1 and Ausiello et al. (2003) doesn't cover the extension of the theory to real-valued optimization problems. I didn't ask it explicitly, but the question could also be how the theory on rational-valued optimization problems (described in Ausiello et al., 2003) extends to real-valued problems (e.g. in terms of definitions). $\endgroup$ Sep 6, 2021 at 12:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.