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?

• Yuval Filmus: Can you add the definition of strongly NP-hard and strongly NP-complete?
• bonanza: @YuvalFilmus Unfortunately, the authors of the work in which $Y$ is shown to be strongly NP-hard do not give their definition of this. I therefore assumed that they use the definition also given in en.wikipedia.org/wiki/Strong_NP-completeness.
• Yuval Filmus: You cannot show that a problem is NP-hard using the reductions you mention in (2). NP-hardness is defined using many-one reductions rather than using oracle reductions.
• bonanza: @YuvalFilmus, thanks for your reponse. I'm sorry I forgot about the difference between Karp and Cook reductions. I actually meant Karp reductions. I will change the question.
• user12859: A Karp reduction to "a known NP-complete problem" does not show NP-hardness. ​ (You need a reduction from an NP-hard problem.) ​ ​ ​ ​

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