GATE CS 2009 Q14 — Regular and Context-free Languages

By definition, a problem $\pi_A$ is NP-complete if and only if it satisfies two conditions:

1. $\pi_A \in \text{NP}$
2. $\pi_A$ is $\text{NP-hard}$

We are given that $\pi_A$ belongs to the class $\text{NP}$. Therefore, if $\pi_A$ is also $\text{NP-hard}$, it is by definition $\text{NP-complete}$. This makes Option C correct.

Analysis of other options:

• Option A is FALSE: Since $\text{P} \subseteq \text{NP}$, any problem in $\text{P}$ (such as finding the shortest path in a graph) also belongs to $\text{NP}$ and has a polynomial-time algorithm.
• Option B is FALSE: If a problem $\pi_A \in \text{NP}$ can be solved in polynomial time, it simply means $\pi_A \in \text{P}$. This does not imply $\text{P} = \text{NP}$ unless $\pi_A$ is also $\text{NP-complete}$.
• Option D is FALSE: Every problem in $\text{NP}$ can be solved by a non-deterministic Turing machine in polynomial time, which implies it is decidable. Thus, no problem in $\text{NP}$ can be undecidable.