If an NP-hard problem is a special case of problem A, can we conclude problem A is NP-hard?

853 Views Asked by At

Problem B is a special case of Problem A (problem A has additional variables $v_{additional}$ in comparison to problem B). This means for a specific value of $v_{additional}$, problem A is exactly the same as problem B. We know problem B is NP-hard. Can we conclude problem A is also NP-hard?

1

There are 1 best solutions below

4
On BEST ANSWER

By "additional variable" do you mean "additional parameter"? That is, an instance of $A$ specifies a value of $v_{additional}$, and for each instance of $B$ there is an instance of $A$ (with the value of $v_{additional}$ depending in a known way on the instance of $B$) such that the solutions of these instances of $A$ and $B$ are the same?

To expand slightly on Hagen's idea:

Suppose there is an algorithm that solves problem $B$ in time $T(n)$ where $n$ is the size of the instance. Let an instance of $A$ consist of an instance of $B$ plus an additional parameter $v_{additional}$ which does nothing but take up space, in fact $T(n)$ bits of space. Thus the size of this instance of $A$ is $n + T(n)$. Then problem $A$ is in the class $P$: an algorithm of linear time complexity in the size of the instance consists of throwing away $v_{additional}$ and solving the instance of $B$.