# A conceptual question regarding hardness proofs by reduction [closed]

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?

Thanks.

• What do you mean by ​ "reduce a solution" ? ​ ​ ​ ​ – user6973 Jun 15 '17 at 4:41
• 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 – swingballchamp42 Jun 15 '17 at 7:17
• "solution set of S" ... ​ Does that mean S is a search problem? ​ ​ ​ ​ – user6973 Jun 15 '17 at 7:29
• By solution set I mean the set of all possible solutions to S. S is a minimisation problem, as is P – swingballchamp42 Jun 15 '17 at 7:33
• Is ​ "the input domain" ​ the things the solver might receive as input, or the things the objective function might receive as input? ​ ​ ​ ​ – user6973 Jun 15 '17 at 7:56

• 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. – Mohemnist Jun 15 '17 at 8:49
• 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. – Mohemnist Jun 15 '17 at 9:29