سوال ۵۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۲

Use the standard definitions of the complexity classes and the fact that $P \subseteq NP$.

Statement (a): Every NP-complete problem is NP-hard. — TRUE.

By definition, a problem $X$ is NP-complete iff

$X \in NP \quad\text{and}\quad X \text{ is NP-hard}.$

So NP-completeness requires NP-hardness; the implication $\text{NP-complete} \Rightarrow \text{NP-hard}$ holds for every such problem.

Statement (b): Every NP-hard problem is NP-complete. — FALSE.

NP-hard means "at least as hard as every problem in NP" (every $L \in NP$ reduces to it in polynomial time), but an NP-hard problem need not itself lie in $NP$. Classic counterexample: the Halting Problem is NP-hard yet undecidable, so it is not in $NP$ and therefore not NP-complete. Hence the inclusion $\text{NP-hard} \subseteq \text{NP-complete}$ fails.

Statement (c): Every problem in P is also in NP. — TRUE.

$P \subseteq NP.$

A polynomial-time decider is, in particular, a polynomial-time verifier (it just ignores the certificate), so any language solvable in polynomial time is verifiable in polynomial time. Thus every P problem is an NP problem (whether the inclusion is strict — the $P \overset{?}{=} NP$ question — is open, but $P \subseteq NP$ is certain).

Conclusion. Statements (a) and (c) are correct, (b) is not. The answer is (a) and (c) — option 2.

Pitfall: Don't confuse NP-hard with NP-complete. NP-complete $=$ NP-hard $\cap$ NP; NP-hard alone allows problems strictly harder than NP (even undecidable ones), so "NP-hard $\Rightarrow$ NP-complete" is false.