Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$?

Question

I am having problems resolving the following question:

Given some problem $X$. If there exists a polynomial time reduction from (for example) $\mbox{SAT}$ to $X$, $(\mbox{SAT} \leq_{p} X)$ and since we know that $\mbox{SAT}$ is $\mbox{NP-complete}$, to show that $X$ is $\mbox{NP-complete}$ is it necessary to show that $X\in \mbox{NP}$ via some third party algorithm?

If yes, then why?

Answer 1

the reduction only shows that X is at least as hard as SAT (NP-HARD). This could mean that X is in a class suspected to be harder than NP such as PSPACE or EXPTIME. To show that X is NP-complete you must show that it is also in NP. If you try it out you will see that you can easily reduce SAT to problems in EXPTIME that are not suspected to be in NP. The idea being that your reduction shows that X is at least as hard as SAT, but there are classes of problems harder than NP problems which X could fall into.

Answer 2

Here is a very general negative answer. Consider the following language: $$ L = \{\langle M,x,o \rangle : M \text{ outputs } o \text{ on input } x\}, $$ where $o \in \Sigma^* \cup \{ \bot \}$ and $\langle \cdot,\cdot,\cdot \rangle$ is any polytime pairing function (we can even demand it to be logspace, or even weaker). Every language accepted by some Turing machine can be reduced to $L$ in polytime, yet $L$ is not computable.