-1
$\begingroup$

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.

$\endgroup$

closed as off-topic by Kaveh, Marzio De Biasi, Emil Jeřábek, Sasho Nikolov, Lev Reyzin Jun 15 '17 at 16:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Marzio De Biasi, Emil Jeřábek, Sasho Nikolov, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
2
$\begingroup$

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.

$\endgroup$
  • $\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.