Is there any relationship of hardness between the two problems?

Question

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?

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