<p>What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show that given a constant $x$ deciding whether $y \leq k$ is NP-Hard and given a constant $y$, deciding whether $x \leq k$ is NP-Hard. </p>

<p>What is the best way of stating this result? $P$ is NP-Hard to solve? Or should the statement be more specific? Furthermore, for such two parameter decision problems, what <em>should</em> be proven if we want to obtain an NP-Hardness result? A result of the type I proved or a result that proves it is NP-Hard to decide if $x + y \leq k$ etc. </p>

CC BY-SA 4.0
2018-05-10T06:23:54.267Z
What do you mean by "given a fixed $x$"?  Do you mean that $x$ is part of the input?  Or that when $x$ is a fixed constant, like 3, the problem is NP-hard?  Those are two different situations, and it's important to keep them clear in your head.  What does it mean to "minimize two parameters"?  You can't simultaneously minimize two parameters.  For an optimization problem to be well-defined, you need to identify a single objective function that you want to minimize, or in some other way specify how to trade off between the two parameters.
D.W.
CC BY-SA 4.0
2018-05-11T20:12:11.590Z
By fixed I mean a constant. It is NP-hard to decide $y \leq k$ when x is constant and vice versa.
user1246462
<cc.complexity-theory><np-hardness>
Best way to represent NP-Hardness result for decision problem with two decision parameters
user1246462
# Best way to represent NP-Hardness result for decision problem with two decision parameters

(Asked by: username_0 on 2018-05-09)

What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show that given a constant $x$ deciding whether $y \leq k$ is NP-Hard and given a constant $y$, deciding whether $x \leq k$ is NP-Hard.

What is the best way of stating this result? $P$ is NP-Hard to solve? Or should the statement be more specific? Furthermore, for such two parameter decision problems, what *should* be proven if we want to obtain an NP-Hardness result? A result of the type I proved or a result that proves it is NP-Hard to decide if $x + y \leq k$ etc.

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: What do you mean by "given a fixed $x$"?  Do you mean that $x$ is part of the input?  Or that when $x$ is a fixed constant, like 3, the problem is NP-hard?  Those are two different situations, and it's important to keep them clear in your head.  What does it mean to "minimize two parameters"?  You can't simultaneously minimize two parameters.  For an optimization problem to be well-defined, you need to identify a single objective function that you want to minimize, or in some other way specify how to trade off between the two parameters.  
> **username_0**: By fixed I mean a constant. It is NP-hard to decide $y \leq k$ when x is constant and vice versa.  

---

## 0 answers

