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?
2026-03-26 06:28:38.1774506518
If an NP-hard problem is a special case of problem A, can we conclude problem A is NP-hard?
853 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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$.