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:
- Show that problem $X$ is in NP (polynomial time verifiable)
- 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$
- 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?