Skip to main content
Computer Science

Return to Question

edited title
Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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

deleted 12 characters in body; edited tags
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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

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

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?

Post Migrated Here from cstheory.stackexchange.com (revisions)
Source Link
user6697
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