<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-06-15T07:29:28.363Z
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??
swingballchamp42
CC BY-SA 3.0
2017-06-15T08:49:32.000Z
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
CC BY-SA 3.0
2017-06-15T08:57:29.187Z
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?
swingballchamp42
CC BY-SA 3.0
2017-06-15T09:29:51.903Z
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
CC BY-SA 3.0
2017-06-15T09:30:22.273Z
A good example is reducing SAT to 3-SAT.
Mohemnist
CC BY-SA 3.0
2017-06-15T05:50:33.167Z
2017-06-15T05:50:33.167Z
Mohemnist
<p>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?</p>

<p>I suspect that the answer is no, but I thought I might aswell ask.</p>

<p>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?</p>

<p>Thanks.</p>

CC BY-SA 3.0
2017-06-15T07:17:00.190Z
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
CC BY-SA 3.0
2017-06-15T07:33:03.927Z
By solution set I mean the set of all possible solutions to S. S is a minimisation problem, as is P
swingballchamp42
CC BY-SA 3.0
2017-06-15T08:03:21.367Z
Apologies for not being clearer - in this case I meant the input domain   to be the set of all instances of P that might be given to a solver as input. In this particular example, I meant for the input domain (with respect to the above definition) of P to be the set of all possible directed graphs, and for the input domain of S to be a subset of this set - the set of all directed acyclic graphs
swingballchamp42
<graph-theory><graph-algorithms><np-hardness><reductions><complexity-theory>
A conceptual question regarding hardness proofs by reduction
swingballchamp42
# A conceptual question regarding hardness proofs by reduction

(Asked by: username_0 on 2017-06-15)

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.

**Tags:** graph-theory, graph-algorithms, np-hardness, reductions, complexity-theory

> **Comments:**
> **username_0**: 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  
> **username_0**: By solution set I mean the set of all possible solutions to S. S is a minimisation problem, as is P  
> **username_0**: Apologies for not being clearer - in this case I meant the input domain   to be the set of all instances of P that might be given to a solver as input. In this particular example, I meant for the input domain (with respect to the above definition) of P to be the set of all possible directed graphs, and for the input domain of S to be a subset of this set - the set of all directed acyclic graphs  

---

## 1 answers

### Answer by username_1 on 2017-06-15. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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??  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: A good example is reducing SAT to 3-SAT.  

---

