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

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?

-

## migrated from cstheory.stackexchange.comFeb 5 '13 at 21:08

This question came from our site for theoretical computer scientists and researchers in related fields.

Read again the definition of NP-Completeness. If you still don't get it, let X = QSAT and think on your question again. –  chazisop Feb 5 '13 at 12:44

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.