4
$\begingroup$

Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.

Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y are two sets of variables.

Another problem P2: With y and D as input, computes $x^*=argmax_xF(x|y,D)$.

If we know P2 is NP-hard, can we infer the hardness of P1? Is P1 also NP-hard?

$\endgroup$
  • 1
    $\begingroup$ Please explain your notation. The statement of P2 is unclear, what does $x\mid y$ mean? $\endgroup$ – Jan Johannsen Oct 5 '16 at 7:53
  • $\begingroup$ @JanJohannsen Sorry for the abused notation, F(x|y,D) means "given y and D as input, F as a function of x only"; similarly, F(x, y | D) means "given D as input, F as a function of x and y". $\endgroup$ – user2789928 Oct 5 '16 at 16:37
8
$\begingroup$

No, you cannot infer hardness of P1. (And your question looks suspiciously close to homework.) Consider the special case where

  • $D$ is an undirected graph $G=(V,E)$
  • $x$ is a subset $E_x\subseteq E$
  • $y$ is a non-negative integer

The function value $F(x,y,D)$

  • takes the value $2$, whenever $y\ge1$;
  • takes the value $1$, if $y=0$ and if $E_x$ induces a Hamiltonian cycle in $G$;
  • takes the value $0$, if $y=0$ and if $E_x$ does not induce a Hamiltonian cycle in $G$.

Fact. The problem P1 of maximizing $F$ for a given graph $G$ is polynomially solvable.

(Just pick $E_x=\emptyset$ and $y=1$ to reach an objective value of $2$.)

Fact. The problem P2 of maximizing $F$ for a given graph $G$ and a given number $y$ is NP-hard.

(By fixing $y=0$, the problem becomes the NP-hard Hamilton cycle problem.)

$\endgroup$
  • $\begingroup$ Many thanks to your explanation! But it is not for homework:) $\endgroup$ – user2789928 Oct 5 '16 at 19:02

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.