Skip to main content
1 of 3
user6697
  • 337
  • 1
  • 2
  • 6

Does reduction form 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?

Thank you

user6697
  • 337
  • 1
  • 2
  • 6