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

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?

• Yes. Fix an NP problem P. Since B is NP-hard, any instance of P can be reduced to an instance of B in polynomial time. But every instance of B is at the same time an instance of A. So we can reduce instance of P to A. – Wojowu Jul 29 '16 at 15:17
• Is $v_{additional}$ always the same fixed value or might it depend on the B-problem hidden in the A-problem? In the lattre case, if the size grows fast enough in the size of the B-problem, it may be possible to have a polynomial algorithm for A that still would produce an exponential algorithm for B – Hagen von Eitzen Jul 29 '16 at 15:20
• @HagenvonEitzen: Problem B has $n$ inputs, problem A has $2n$ inputs. The extra $n$ variables are some kind of weight which can take any number. If 0 is assigned to these $n$ weights, problem A turns to B. These weights in general can be any number and do not depend on B – ladan Jul 29 '16 at 18:49

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?
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$.
• Problem B has $n$ parameters, problem A has $2n$ parameters. The extra $n$ parameters are some kind of weight which can take any number. If 0 is assigned to these $n$ weights, problem A turns to B. These weights in general can be any number and do not depend on B. Problem B is actually maximum coverage problem. – ladan Jul 29 '16 at 19:01
• If every instance of B is an instance of A (with the $n$ extra parameters set to 0), that is a polynomial-time reduction from B to A. – Robert Israel Aug 2 '16 at 16:48