Complexity Theory in Theory of Computation: P, NP, NP-Completeness and Worked Examples

Complexity theory is often reduced to a list containing P, NP and NP-complete. You may remember the arrows yet still be unable to say what the input is, which resource is bounded or which way a reduction transfers hardness. Big-O analysis is only the entry point: complexity theory classifies decision problems by the resources needed to solve or verify them. Three things settle almost every question in the area: the encoded length of the input, whether the polynomial bound applies to solving or only to verifying, and which way the reduction arrow points.

Complexity theory: from computable problems to feasible problems

Computability asks whether an algorithm decides a language; complexity asks what time or space it needs as input grows. Turing Machines and Decidability: Recursive vs RE, and the Halting Problem covers the undecidable boundary. The relevant bounds for decidable problems are time and space.

A problem is a language of encoded yes-instances. For binary string x, input length is n = |x|. Deterministic time T(n) is the maximum steps for any length-n input; space S(n) is the maximum work space. Measure worst-case encoded length, not the printed numeric value.

For graph G, asking whether it has a clique of size at least k is decision. Finding one is search; finding the largest is optimisation. Complexity classes are defined most cleanly for decision problems.

Time complexity and input size: polynomial is a growth class

O, Omega and Theta give upper, lower and tight asymptotic bounds. Constants and lower-order terms disappear in growth classes, not exact counts. n^k is polynomial for fixed k; 2^n is exponential.

Compare A(n) = 3n^2 + 5n + 7 with B(n) = 2^n:

Thus A is Theta(n^2) and B is Theta(2^n). Polynomial does not always mean practical.

Encoding can change the class. N = 1,000,000 needs ceil(log2(N + 1)) = 20 bits because 2^19 < 1,000,001 <= 2^20. A loop through 1 to N takes 1,000,000 iterations, linear in value N but exponential in 20-bit input length.

P, NP and co-NP: solving, verifying and complementing

P contains decision problems solvable deterministically in polynomial time. In NP, yes-instances have polynomial-size certificates verifiable deterministically in polynomial time. Equivalently, a nondeterministic machine decides them in polynomial time. We know P subseteq NP; NP does not mean "non-polynomial".

For V = {A,B,C,D,E}, E = {AB, AC, BC, BD, CE, DE} and Vertex Cover bound k = 3, certificate C = {B,C,D} has size 3. Scan the edges: AB is covered by B; AC by C; BC by B or C; BD by B or D; CE by C; DE by D. This polynomial verification proves membership in NP, not P.

co-NP contains languages whose complements are in NP. SAT is in NP; UNSAT and TAUT illustrate co-NP. We know P subseteq NP intersection co-NP. NP and co-NP are not disjoint; their equality is unresolved.

Polynomial reductions and NP-completeness: reduce 3-SAT to CLIQUE

A <=p B is a polynomial-time mapping f with x in A exactly when f(x) in B. A solver for B solves A. If NP-hard A <=p B, hardness transfers to B; reducing B to A does not prove B hard.

For Phi = (x or y or not z) and (not x or y or z) and (x or not y or z), create one column per clause:

• C1: a1=x, a2=y, a3=not z

• C2: b1=not x, b2=y, b3=z

• C3: c1=x, c2=not y, c3=z

Add no within-clause edge. Join cross-clause vertices whose literals are not complementary:

• C1 to C2: a1-b2, a1-b3, a2-b1, a2-b2, a2-b3, a3-b1, a3-b2

• C1 to C3: a1-c1, a1-c2, a1-c3, a2-c1, a2-c3, a3-c1, a3-c2

• C2 to C3: b1-c2, b1-c3, b2-c1, b2-c3, b3-c1, b3-c2, b3-c3

Of 27 cross-clause pairs, exclude complementary pairs a1-b1, a3-b3, a2-c2, a3-c3, b1-c1, b2-c2. This leaves 27 - 6 = 21 edges. Set k = 3.

{a1,b2,c3} is a clique because a1-b2, a1-c3 and b2-c3 exist. Literals x, y, z give satisfying assignment x=true, y=true, z=true. Conversely, no within-clause edges force a 3-clique to select one consistent, non-complementary literal per clause, producing a satisfying assignment.

For m clauses, 3m vertices and at most 9m(m-1)/2 cross-clause pairs make the construction polynomial. CLIQUE is itself in NP: a claimed clique of size k is checked by confirming k(k-1)/2 edges. Hardness inherited from 3-SAT plus that membership is what makes CLIQUE NP-complete rather than merely NP-hard.

Complexity-class map: NP-hard is not NP-complete

Known containments are P subseteq NP subseteq PSPACE subseteq EXPTIME and P subseteq co-NP. Polynomial time uses polynomial space; polynomial-space computation may run longer. The arrows are not strict separations. P = NP is unresolved.

Every NP problem reduces to an NP-hard problem. NP-complete means NP-hard and in NP; SAT and CLIQUE are standard examples. NP-hard problems may lie outside NP or be undecidable. A polynomial-time algorithm for one NP-complete problem gives P = NP.

Complexity theory traps: why wrong answers feel plausible

{B,C,D} verifies quickly without establishing a solver. 3-SAT <=p CLIQUE makes CLIQUE at least as hard as 3-SAT. A(20) = 1,307 is exact; Theta(n^2) is growth. The loop is exponential in 20-bit length. Use subset arrows for P, NP and co-NP, marking unresolved equalities.

How GATE-style questions and interviews test complexity theory

Questions classify solvers or verifiers, test encoding, check certificates, follow reductions or separate hardness from completeness. Interviews ask the same content in a different shape: recognise the problem on the whiteboard as a known NP-complete one, then say what you would ship anyway, which is where approximation guarantees, heuristics and exact solvers on small parameters belong. Regular Expressions and the Pumping Lemma, with the Exam Angle covers the earlier layer, where the question is which languages a machine can recognise at all rather than what recognising them costs.

Three direction checks are worth deriving:

1. A <=p B and B in P imply A in P: reduce, then solve B.

2. NP-hard A and A <=p B imply NP-hard B: every NP problem reaches B through A.

3. NP-complete A, A <=p B and B in NP make B NP-complete: hardness plus membership.

Solve in five steps: identify encoding and n; mark solving or verification; write the reduction arrow; separate hardness from membership; apply known containments. Drill with Theory of Computation MCQs. Over 60 practice questions sit under Complexity Theory alone, which is enough repetition to make the direction checks automatic. GATE CS Exam Preparation shows the wider line-up.

Complexity theory: the short version and next step

Recall: encoding fixes n; bounds classify growth; P means polynomial-time solving; NP means polynomial-time verification of yes-certificates; reductions transfer algorithms and hardness; NP-complete means NP-hard plus NP membership.

Reproduce A(20) = 1,307, B(20) = 1,048,576, certificate {B,C,D}, 9 vertices, 21 edges and clique {a1,b2,c3} for k=3. If one fails, return to its derivation.

For a sequenced route through Complexity Theory and the wider curriculum, use GATE Guidance by Sanchit Sir. Otherwise, reproduce both examples unaided, then take the same five steps into timed practice.