Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

migrated from Feb 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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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