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

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

<p>The function value $F(x,y,D)$ </p>

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

<blockquote>
  <p><strong>Fact.</strong> The problem P1 of maximizing $F$ for a given graph $G$ is polynomially solvable.</p>
</blockquote>

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

<blockquote>
  <p><strong>Fact.</strong> The problem P2 of maximizing $F$ for a given graph $G$ and a given number $y$ is NP-hard.</p>
</blockquote>

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

CC BY-SA 3.0
2016-10-05T19:02:21.587Z
Many thanks to your explanation! But it is not for homework:)
user2789928
CC BY-SA 3.0
2016-10-05T09:22:54.917Z
2016-10-05T09:22:54.917Z
Gamow
<p>Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2016-10-05T07:53:19.297Z
Please explain your notation. The statement of P2 is unclear, what does $x\mid y$ mean?
Jan Johannsen
CC BY-SA 3.0
2016-10-05T16:37:19.627Z
@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".
user2789928
<cc.complexity-theory><np-hardness><computability><np>
Is there any relationship of hardness between the two problems?
user2789928
# Is there any relationship of hardness between the two problems?

(Asked by: username_0 on 2016-10-05)

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?

**Tags:** cc.complexity-theory, np-hardness, computability, np

> **Comments:**
> **username_1**: Please explain your notation. The statement of P2 is unclear, what does $x\mid y$ mean?  
> **username_0**: @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".  

---

## 1 answers

### Answer by username_2 on 2016-10-05. Score: 8 | Accepted answer

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

> **Comments:**
> **username_0**: Many thanks to your explanation! But it is not for homework:)  

---

