P, NP and Polynomial-Time Reducibility: Definitions, Direction and a Worked Example

Learners often memorise P, NP, NP-hard, and NP-complete as four labels, then reverse the reduction arrow when a question asks what follows from it. One usable mental model fixes this: separate solving from verification, then read A <=p B as "use a solver for B to solve A". We will test that model on VERTEX-COVER <=p INDEPENDENT-SET and finish with an exam-proof checklist.

The CS Fundamentals hub places these ideas alongside the other foundations they depend on.

1. P, NP, NP-hard and NP-complete: build the map first

These classes concern decision problems, whose answer is YES or NO. P contains problems solvable by a deterministic algorithm in time polynomial in the encoded input length. NP contains problems whose YES instances have polynomial-size certificates verifiable in polynomial time.

P is a subset of NP. A problem is NP-hard if every problem in NP polynomially reduces to it. A problem is NP-complete when it is in NP and NP-hard, so NP-complete = NP intersect NP-hard. An NP-hard problem need not be in NP. Whether P = NP remains unresolved, so P != NP is not proved.

Keep this compact ladder in mind:

• P: easy to solve in polynomial time.

• NP: a YES certificate is easy to verify in polynomial time.

• NP-hard: at least as hard as every problem in NP under polynomial reductions.

• NP-complete: both in NP and NP-hard.

These labels describe formal relationships, not how difficult one small example feels.

2. What polynomial time means: a concrete P instance

Consider directed reachability with V = {s, a, b, c, t} and E = {s->a, s->b, a->c, b->c, c->t}. Does a directed path exist from s to t?

Breadth-first search starts with [s]. After expanding s, the queue is [a,b]. After a, it is [b,c]. Expanding b leaves [c] because c is already discovered. Expanding c gives [t], so the answer is YES via s->a->c->t. The path s->b->c->t also works.

The running-time bound is O(|V|+|E|). Here, |V|=5 and |E|=5, but polynomial time describes growth with input size, not how quickly this instance finishes. Review Time Complexity: Big-O, Theta, Omega & Master Theorem if the notation needs refreshing.

3. What NP verification means: check a supplied certificate

Take decision SUBSET-SUM with numbers [3, 7, 10, 14, 18], target 31, and certificate [1, 0, 1, 0, 1]. A 1 selects that position, so positions 1, 3, and 5 contribute 3, 10, and 18.

The verifier performs clear, bounded work:

1. Confirm that the certificate has five bits.

2. Select the values marked by 1.

3. Compute 3 + 10 + 18 = 31.

4. Compare the result with the target 31 and accept.

In general, the verifier scans the certificate and performs arithmetic polynomial in the encoded input length. This certificate proves a YES instance. It does not show how to discover a certificate efficiently for every input. That difference between checking and searching is the central distinction here. NP means nondeterministic polynomial time, commonly expressed through polynomial-time verification, not "non-polynomial".

4. NP-hard and NP-complete are about reductions

A problem B is NP-hard when every problem in NP can be polynomially reduced to B. To call B NP-complete, we must separately prove B in NP, usually by describing a polynomial-time verifier for its YES certificates.

These are separate proof obligations.

This concerns tractability, not merely algorithms that seem slow. It is also different from the computability questions covered in Turing Machines: Design, Worked Trace, Decidability. A decidable problem may require expensive computation, while an undecidable problem sits outside the ordinary NP-complete decision-problem claim.

The central consequence is conditional: if any NP-complete problem receives a polynomial-time algorithm, every problem in NP can use its reduction to that problem, giving P = NP. No such result is known. It is also not proved that every NP-complete problem must take exponential time.

5. Read A <=p B in the correct direction

A polynomial-time many-one reduction from A to B is a function f, computable in polynomial time, such that x is a YES instance of A if and only if f(x) is a YES instance of B.

Read A <=p B aloud as: "A reduces to B; a B-solver can answer A after the transformation." Retain two inference patterns:

• If A <=p B and B in P, then A in P.

• To prove a new problem B is NP-hard, start with a known NP-hard problem A and prove A <=p B.

Showing B <=p A points the wrong way for that proof. Check three things: the transformation runs in polynomial time, YES maps to YES, and NO maps to NO. Equivalently, prove the full biconditional. The next section checks all three.

Hardness flows towards the problem being proved hard here.

6. Worked reduction: VERTEX-COVER to INDEPENDENT-SET

Use the graph V = {A, B, C, D, E} and E = {AB, AC, BC, CD, DE}. It is a triangle A-B-C-A with a tail C-D-E. Start with VERTEX-COVER instance (G, k=3). Transform it to (G, k'=|V|-k) for INDEPENDENT-SET. k'=5-3=2. The graph stays unchanged. Do not construct its complement graph.

A set C covers every edge if and only if V\C contains no edge. If C is a cover with |C| <= k, then I=V\C is independent and |I| >= |V|-k. Conversely, if I is independent with |I| >= |V|-k, then C=V\I covers every edge and |C| <= k. Thus a cover of size at most k exists if and only if an independent set of size at least |V|-k exists. Copying G and computing the target takes polynomial time.

Choose C={A,C,D} for the YES case:

• AB is covered by A.

• AC is covered by A or C.

• BC is covered by C.

• CD is covered by C or D.

• DE is covered by D.

Its complement is I={B,E}. Since BE is not in the edge set, I is independent, and |I|=2=k'.

Check a NO case on the same graph. If k=2, then k'=5-2=3. An independent set can contain at most one vertex from the triangle {A,B,C}. It can also contain at most one of {D,E} because DE is an edge. Therefore every independent set has size at most 2, so none has size 3. By the proved equivalence, no vertex cover of size at most 2 exists.

7. How exams test the idea, and the traps that cost marks

Questions may ask you to classify a problem, choose a consequence of A <=p B, identify the obligations in an NP-completeness proof, or check whether a certificate or reduction preserves YES and NO. Those obligations are B in NP and A <=p B from a known NP-hard problem.

Correct these common traps:

Keep undecidability separate. Rice's Theorem for GATE: Two-Part Undecidability Test helps with that boundary, but does not replace an NP-hardness proof. KnowledgeGate has 60+ published practice questions tagged to P, NP and reducibility.

8. The short version and the next study step

• P means polynomial-time solving.

• NP means polynomial-time verification of YES certificates.

• A <=p B means a B-solver can solve A after a polynomial-time transformation.

• NP-completeness needs both membership in NP and NP-hardness.

For the five-vertex graph, k=3 becomes k'=5-3=2, and cover {A,C,D} complements independent set {B,E}. Continue with Theory Of Computation / Automata Theory for focused study. If you are rebuilding several CS foundations, ZERO TO HERO is the broader route. Before practising, redo the reduction with k=2 and explain why target 3 gives a NO instance.