An easy question about NP-hard

Question

Consider an optimization problem includes two variables. If we fix the value of one variable, then the optimization problem over the other variable is NP-hard. Can it be concluded that the original problem over two variables is always NP-hard?

Answer 1

No, this cannot be concluded. What you are describing is not a strict restriction of the problem. I will give a counter example.

Suppose you have a problem $A$ that takes an input $n$ that characterizes a two variable function $f$, and that outputs $(x,y)$ such that $f(x,y)$ is of maximal value. Further suppose that a problem $B_c$ does the same thing for a constant $c$ in the range of $f$'s first input, except it outputs $y$ that maximizes $f(c,y)$. Finally, suppose that $B_c$ is NP-hard. This is the context of the question as I understand it from the post and a clarification in comments.

Now, suppose $f$ as characterized by the input $n$ is maximal at $(n,n)$. Then $A$ is a constant time problem.

It is not inconsistent to also suppose, fixing $c$, that any NP problem with input $m$ is equivalent to some problem $B_c$ with input $m^\prime$ for some $m^\prime$. Sure, if $m^\prime$ happens to equal $c$, then that special case is constant time. However, this need not be the case, and then the universally optimal $(m^\prime,m^\prime)$ is irrelevant, as it is not a valid response for an algorithm solving $B_c$.

Thus any NP-problem can be reduced to $B_c$ for any $c$, and so all $B_c$ are NP-hard.