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?

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

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.