Proving complexity by reduction using strongly NP-hard problem

Question

I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard.

I tried to follow the same procedure as for proving NP-completeness which I try to summarize here:

1. Show that problem $X$ is in NP (polynomial time verifiable)
2. Make the Karp reduction from a known NP-complete problem by finding a poly-time algorithm that transforms the instances $y$ of $Y$ to instances $x$ of $X$
3. Show correctness of algorithm: Show that for every yes/no answer to an instance of $Y$, the algorithm also returns yes/no

The problem I'm currently facing concern point 1 and 2:

• I'm sure that $X$ is in NP, but $Y$ is not necessarily, right? Is it a problem when I try to reduce an NP-hard problem to an NP-complete one?
• The strongly NP-hard problem $Y$ is not necessarily NP-complete, right? Can I still use $Y$ here?

Another open question regards the fact that $Y$ is strongly NP-hard:

• Assuming that I can do the reduction as outlined above, is then $X$ also strongly NP-complete?

Answer 1

I will assume that your definition is the one on Wikipedia.

We wish to prove that $X$ is strongly NP-Complete. Here's how you do that. First, show that $X$ is strongly NP$^1$. Next, find a strongly NP-Complete problem $Y$ and reduce $Y$ to $X$. That is, provide an algorithm which takes an instance $y$ of $Y$ and produces $f(y)$ such that if $y\in Y$ then $f(y)\in X$ and otherwise, if $y\not\in Y$ then $f(y)\not\in X$.

I remember in which way to reduce a problem (was it $X$ to $Y$ or $Y$ to $X$?) by framing it as a conversation which I've laid out here in this other answer(link): someone challenges me by saying $X$ is easy. Then I say, nonsense, if $X$ were easy, then I could solve very hard problem $Y$. And then I show how to do that: I take an instance of $Y$, rewrite it into an instance of $X$, and then you're done. You've shown that $X$ is at least as hard as $Y$, so we write $Y\leq X$.

$^1$ best I can figure, strongly NP means it has logarithmically-sized certificates