Given :
$S$ is an $NP-Complete$ problem
$Q$ and $R$ are two other problems not known to be in $NP$.
$Q$ is polynomial-time reducible to $S$ and $S$ is polynomial-time reducible to $R$.
My thoughts so far-
For $Q$ to be $NP-Complete$, by formal definitions, $Q$ must be in $NP$ and all other problems in $NP$ must be reducible to $Q$ in polynomial-time.
1. How to prove that $Q$ is in $NP$?
2. Is $R$ in $NP-hard$?
2026-03-25 16:06:03.1774454763
NP-Completeness and NP
87 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Think of what the definitions of "NP", "NP-complete" and "NP-hard" mean.
NP means: Easy enough to be solved in polynomial time by a non-deterministic computer.
NP-hard means: Hard enough so that every problem in NP can be solved by converting it to our problem in polynomial time, solving the problem, and converting the solution back in polynomial time. "x is NP-hard" <=> "Every problem y in NP is polynomial time reducible to x".
NP-complete means: Easy enough to be in NP, but hard enough to be NP-hard. "x is NP-complete" <=> "x is in NP and x is NP-hard".
Actually, you can now answer the question without any understanding what NP, NP-complete and so on mean, just from the definitions of NP-hard and NP-complete.