# P vs NP question from GeeksforGeeks

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?

• If Q can be reduced in polynomial time to a problem in NP, then Q is also in NP. – Pontus May 10 '19 at 16:08
• @Pontus Yeah I figured, the 'Q not known to be in NP' really threw me off. – Freud May 10 '19 at 18:48
• 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. – 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).