0

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?

ladan
  • 73
  • 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

1 Answers1

0

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$.

Robert Israel
  • 448,999
  • 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
  • In that case Wojowu's comment applies. – Robert Israel Jul 29 '16 at 20:10
  • Problem B is an instance of A, however A is not an instance of B. So I don't think Wojowu's comment applies here. I cannot reduce B to A – ladan Aug 02 '16 at 15:02
  • 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 02 '16 at 16:48