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.

  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. May 10 '18 at 6:23
  • $\begingroup$ By fixed I mean a constant. It is NP-hard to decide $y \leq k$ when x is constant and vice versa. $\endgroup$ – user1246462 May 11 '18 at 20:12

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.