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?

  • 1
    $\begingroup$ Please explain your notation. The statement of P2 is unclear, what does $x\mid y$ mean? $\endgroup$ Oct 5, 2016 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$ Oct 5, 2016 at 16:37

1 Answer 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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