From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (GATE CS 2006)

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

The answer they give is B and I can see that. But I'm curious as to what is Q then? If it's not in NP and if it's not in NP hard, is there some other set that I don't know about it belongs to?

  • $\begingroup$ If Q can be reduced in polynomial time to a problem in NP, then Q is also in NP. $\endgroup$ – Pontus May 10 '19 at 16:08
  • $\begingroup$ @Pontus Yeah I figured, the 'Q not known to be in NP' really threw me off. $\endgroup$ – Freud May 10 '19 at 18:48
  • $\begingroup$ Yeah, that's a really badly worded question. Anyone who has a problem that reduces to a problem in NP should know that they're both in NP. $\endgroup$ – David Richerby May 10 '19 at 20:01

In fact, $Q$ is in NP (since you can reduce it to $S$ in poly-time and $S$ is in NP). It's just not necessarily NP-complete or NP-hard.

For example, let's let $Q$ be the following decision problem:

Given a number $n$, is $n$ prime?

This problem is known to be in $P$. But I can reduce it to something NP-complete, like HamiltonianPath:

First, determine whether $n$ is prime (in poly-time).

If it's prime, let $G$ be a graph with two vertices and one edge between them.

If it's not prime, let $G$ be a graph with two vertices and no edges.

Now, pass $G$ to HamiltonianPath, which will give you your answer.

In this case, $Q$ can be reduced to the NP-complete HamiltonianPath, but it clearly isn't NP-hard or NP-complete (since it can be solved in poly-time).


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.