If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input X to a solution to S given input Y and X = Y in polynomial time, does it prove that S is also NP-hard?

I suspect that the answer is no, but I thought I might aswell ask.

Additionally, does a hardness proof always need to involve a reduction from a decision problem, or can we use NP-hard problems to which the solution is of some other form?


  • $\begingroup$ What do you mean by ​ "reduce a solution" ? ​ ​ ​ ​ $\endgroup$ – user6973 Jun 15 '17 at 4:41
  • $\begingroup$ By that I meant establish that there exists a polynomial function f of the output of P given X that such that f(X) equals some Y belonging to the solution set of S $\endgroup$ – swingballchamp42 Jun 15 '17 at 7:17
  • $\begingroup$ "solution set of S" ... ​ Does that mean S is a search problem? ​ ​ ​ ​ $\endgroup$ – user6973 Jun 15 '17 at 7:29
  • $\begingroup$ By solution set I mean the set of all possible solutions to S. S is a minimisation problem, as is P $\endgroup$ – swingballchamp42 Jun 15 '17 at 7:33
  • $\begingroup$ Is ​ "the input domain" ​ the things the solver might receive as input, or the things the objective function might receive as input? ​ ​ ​ ​ $\endgroup$ – user6973 Jun 15 '17 at 7:56

In your question, did you just restrict the input of two problems? If yes, this is wrong. Consider problem A which is NP-complete. You can trivially reduce A to itself! So, do you think a restriction in the input keeps A an NP-complete problem? Definitely not.

For the second question, the formal definition of an NP problem is a decision problem (solvable nondeterministically in a Turing machine with a polynomial time). Therefore, optimization problems are not in class NP and NP-complete. Although, an NP-hard problem can be outside NP, and can be an optimization problem.

  • $\begingroup$ I restricted the input of the first problem so it's input domain matched that of the second problem. Additionally, if prob A is an NP-hard optimisation problem and B is one which I expect to be NP-hard, can I not make a reduction from A to B to prove the NP-hardness of B?? $\endgroup$ – swingballchamp42 Jun 15 '17 at 7:29
  • $\begingroup$ Consider problem $A$ as general SAT (Boolean satisfaction problem) and $B$ as 2-SAT (SAT where every clause has two literals). $A$ is NP-complete, and $B$ is not. If you restrict the input of $A$ to 2-SAT instances which match the inputs of $B$ and make a trivial reduction, this will not result in NP-completeness of $B$, as you may expect. $\endgroup$ – Mohemnist Jun 15 '17 at 8:49
  • $\begingroup$ But say I had 2 problems, A and B, each of which is defined over some input domain with B's input domain being a subset of A's. If A is NP-hard, and I suspect B is too, how would I go about proving it, based on a reduction from A to B? Is it that these two problems need to be defined over the same input domain, so the reduction is not possible? $\endgroup$ – swingballchamp42 Jun 15 '17 at 8:57
  • $\begingroup$ The reduction should reduce EVERY instance of $A$ to an instance of $B$. Since input domains are infinite, you may find a one-to-one map from a set to its subset. $\endgroup$ – Mohemnist Jun 15 '17 at 9:29
  • $\begingroup$ A good example is reducing SAT to 3-SAT. $\endgroup$ – Mohemnist Jun 15 '17 at 9:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.