P vs NP question from GeeksforGeeks

Question

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?

Answer 1

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).