Many students can expand NP as nondeterministic polynomial time and still lose every classification question. The exam usually tests where a problem belongs and which way a reduction arrow must point.
You need one picture of the classes and one rule for reductions. Once those are fixed, most conceptual MCQs become short deductions rather than memory tests.
P, NP, NP-complete and NP-hard, stated precisely
P contains decision problems solvable in polynomial time by a deterministic algorithm. Sorting itself is not a decision problem, but decision questions associated with efficient tasks, such as whether a sorted list contains a key, illustrate the same tractability idea.
NP contains decision problems whose yes-instances have certificates verifiable in polynomial time by a deterministic algorithm. Equivalently, a nondeterministic machine can decide them in polynomial time. NP does not mean "not polynomial". Every problem in P is also in NP because a fast solver makes verification easy.
NP-hard means at least as hard as every problem in NP. Formally, every NP problem can be polynomial-time reduced to an NP-hard problem. An NP-hard problem need not belong to NP and need not even be decidable.
NP-complete means both in NP and NP-hard. These are the hardest decision problems inside NP.
The known containment is P subseteq NP subseteq PSPACE. Whether P = NP remains open. We do not know that P differs from NP, so never present P != NP as a proved theorem.
The class picture and canonical examples
Under the usual diagrammatic assumption that P != NP, draw P inside NP. Put the NP-complete region inside NP but outside P. Draw NP-hard so that it contains the NP-complete region and also extends outside NP.
Examples make the regions usable:
Efficiently solvable problems associated with P include shortest paths with non-negative weights, 2-SAT, matrix multiplication and sorting.
NP-complete decision problems include 3-SAT, Clique, Vertex Cover, Independent Set, Hamiltonian Cycle, Subset Sum and decision TSP.
NP-hard examples outside NP include the undecidable Halting Problem. Optimisation TSP is NP-hard but is not itself an NP decision language.
Decision and optimisation versions must stay separate. "Does a tour of cost at most K exist?" is a decision question and is NP-complete. "Find the minimum-cost tour" is an optimisation problem and is NP-hard.
Polynomial reduction and the direction that matters
Write A <=p B when a polynomial-time computable transformation maps every yes-instance of A to a yes-instance of B and every no-instance of A to a no-instance of B. If you had a polynomial-time solver for B, the transformation would let you solve A in polynomial time too.
That gives two exam rules:
If
A <=p Band B is in P, then A is in P.To prove a new problem B is NP-hard, start from a known NP-hard problem A and show
A <=p B.
The arrow goes from the problem whose hardness you already trust to the problem whose hardness you want to establish. Reducing new B to known-hard A only shows that B is no harder than A. It does not prove B is hard.
This direction is easier to retain if you read the symbol as: "A can be solved using B." If B were easy, A would become easy.
Worked reduction from Independent Set to Vertex Cover
Take the cycle C5 with
V = {1, 2, 3, 4, 5}
and
E = {(1,2), (2,3), (3,4), (4,5), (5,1)}.
For any graph with n vertices, a set S is independent exactly when its complement V minus S is a vertex cover. Why? No edge may have both endpoints inside S, so every edge must have at least one endpoint outside S.
The instance transformation is therefore (G, k) -> (G, n-k). It copies the graph and changes the threshold. It does not need to discover the independent set. Given a witness S, its complement is the corresponding cover.
For C5, let k = 2 and choose S = {1,3}. There is no edge between 1 and 3, so S is independent. Its complement is {2,4,5}, and its size is
n - k = 5 - 2 = 3.
Now verify every edge:
(1,2)is covered by 2.(2,3)is covered by 2.(3,4)is covered by 4.(4,5)is covered by both 4 and 5.(5,1)is covered by 5.
All five edges are covered. Thus C5 has an independent set of size at least 2 exactly when it has a vertex cover of size at most 3. Copying a graph and subtracting the threshold from n takes polynomial time.
Both decision problems are NP-complete. The reduction shows how a yes-answer for one is translated into a yes-answer for the other without solving either during the transformation.
Classification and reduction traps
Three classification questions solved
Question 1: If A <=p B and B is in P, which class must contain A? Answer: P. Transform A's instance to B's instance, run B's polynomial-time solver, and return the same yes or no answer.
Question 2: A is NP-complete, A <=p B, and B is in NP. How should B be classified? Answer: NP-complete. The reduction makes B NP-hard, and the stated membership in NP supplies the second requirement.
Question 3: B reduces to an NP-complete problem A. Does B <=p A prove B is NP-hard? Answer: no. That direction only places B no higher than A under this reduction; B could still be in P.
Reversed arrow: to prove B is NP-hard, use known-hard A <=p B. The reverse direction cannot establish B's hardness.
NP-hard equals NP-complete: false. NP-complete additionally requires membership in NP. The Halting Problem is NP-hard and undecidable, so it is not in NP.
NP means intractable: false. P is contained in NP. For NP-complete problems, no polynomial-time algorithm is known, but that is not a proof that none exists.
P differs from NP: this is a conjecture, not a theorem. Any option claiming the separation has been proved is wrong.
Complements behave automatically: not known. NP is not known to be closed under complement. The complement of an NP-complete language is co-NP-complete, and proving an NP-complete language also lies in co-NP would have major consequences.
The distinction between computation and decidability is developed further in Turing Machines and Decidability. For a familiar polynomial-time technique, Dynamic Programming Explained is a useful contrast to NP-complete search spaces.
How GATE tests complexity classes
Past GATE questions have used single-choice or multiple-select classification, reduction-direction implications, statements about P versus NP, and short questions involving co-NP. When a question gives A <=p B plus membership information, translate the arrow into "a solver for B would solve A" before evaluating the options.
The GATE 2027 CS syllabus does not name NP-completeness as a separate topic. Its Algorithms section lists asymptotic complexity and design techniques, while Theory of Computation lists Turing machines and undecidability. Check the official GATE 2027 test papers and syllabus page before planning revision, and treat this topic as useful for past-question practice and conceptual foundations rather than as an explicitly listed 2027 heading.
Practice in two passes: first separate decision problems from optimisation or function problems, then apply the arrow rule to the exact statement. This prevents a familiar NP-hard example from making a logically unsupported option look true.
The short version and next step
Memorise two lines: NP-complete means in NP and NP-hard. To prove your new problem is NP-hard, reduce a known-hard problem into it.
Build the underlying theory with GATE Guidance by Sanchit Sir, practise classifications in the GATE Test Series, and use the GATE category to connect this topic to the rest of Algorithms.
