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.
A conceptual question regarding hardness proofs by reduction
graph theory;graph algorithms;np hardness;reductions;complexity theory
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.