Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

migrated from cstheory.stackexchange.com Feb 5 '13 at 21:08

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

2 Answers

up vote 3 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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.