Computational Complexity

Theory of Computation & Computer Graphics — Turing Machine, NEC licence examination syllabus (Nepal Engineering Council).

Computational Complexity: sorting problems by "how hard, really?"

Not every solvable problem is EQUALLY solvable — this topic is about that gap.

🎯 P, NP, NP-Complete, NP-Hard

PProblems solvable in polynomial time — considered "efficiently solvable." Example: sorting a list.

NPProblems where a proposed SOLUTION can be VERIFIED in polynomial time, even if finding it might take much longer. Example: given a proposed route, checking if it visits every city (easy) vs actually finding the shortest such route (hard).

NP-CompleteThe "hardest" problems within NP — every other NP problem can be transformed into one of these in polynomial time. If anyone ever finds a fast solution for ANY NP-Complete problem, EVERY NP problem instantly becomes fast too.

NP-HardAt least as hard as NP-Complete problems, but not necessarily required to even BE in NP themselves (may not even be verifiable quickly).

"Is P = NP?" is arguably the single most famous unsolved question in all of computer science — nobody has proven whether every problem whose solution can be quickly VERIFIED can also be quickly SOLVED. A $1 million prize (Millennium Prize) is still waiting for whoever resolves it.

💡 One-liner: "Give a real example of an NP problem and explain why verifying a solution is easier than finding one." → The Traveling Salesman Problem — checking a given route's total distance is fast; finding the guaranteed-shortest route among all possibilities is not.

The distinction the whole question rests on

P and NP are usually presented as two boxes. What makes the famous open question comprehensible is what separates them.

🔍 Finding versus checking

PYou can find the answer quickly.

NPYou can check a proposed answer quickly, even if finding one seems to require trying vast numbers of possibilities.

A jigsaw puzzle is the honest analogy: verifying a completed puzzle takes a glance, while assembling it takes hours. P vs NP asks whether that gap is real — whether there are problems where checking is genuinely easier than finding, or whether we have simply never found the clever algorithm. Nobody has proved either way, and it remains the central open question in the field.

💡 Note that P is contained in NP. If you can find an answer quickly you can certainly check one — just solve it again and compare. The question is only whether the containment is strict, and the overwhelming expectation is that it is, on the grounds that decades of effort have produced no polynomial algorithm for any NP-complete problem.

Why NP-complete matters practically

NP-complete problems are the hardest in NP: every problem in NP reduces to each of them. That gives the class a property worth stating.

A polynomial algorithm for any single NP-complete problem would give one for all of them, and prove P = NP. They stand or fall together — which is why finding one problem intractable is evidence about the whole class, and why recognising that your problem is NP-complete is genuinely useful information rather than defeat.

💡 NP-hard is the wider class: at least as hard as NP-complete, but not necessarily in NP itself — it may not even be decidable. So every NP-complete problem is NP-hard; the reverse fails. A question asking for the difference is testing whether you noticed that NP-complete requires membership in NP as well as hardness.

What to do when a problem is NP-complete

Proving it does not end the work — it changes what "solving" means. The practical routes are to accept an approximate answer with a proven bound, use a heuristic that is usually good with no guarantee, solve only the special cases that actually arise, or accept exponential time on the small inputs where it is affordable.

Syllabus points

Classes P, NP, NP-complete, NP-hard

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.