-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wojowu Jul 29 '16 at 15:17
  • $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Jul 29 '16 at 15:20
  • $\begingroup$ @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 $\endgroup$ – ladan Jul 29 '16 at 18:49
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ladan Jul 29 '16 at 19:01
  • $\begingroup$ In that case Wojowu's comment applies. $\endgroup$ – Robert Israel Jul 29 '16 at 20:10
  • $\begingroup$ 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 $\endgroup$ – ladan Aug 2 '16 at 15:02
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Aug 2 '16 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.