📦
Do you have a pen in your room?
Answer type: YES / NO
If someone shows you the pen, verification is immediate. If not, you may keep searching.
This page builds the idea step by step: everyday questions → solve vs verify → P / NP / NP-Complete / NP-Hard → reductions and SAT to Vertex Cover.
Some questions are easy to answer directly. Some are hard to solve but easy to check. Some may be so general that no algorithm can solve them in every case.
Answer type: YES / NO
If someone shows you the pen, verification is immediate. If not, you may keep searching.
Finding a full solution can take a lot of trial and backtracking.
This feels very different from simply checking a completed grid.
Now the task becomes structured: scan rows, columns, and boxes.
This is the exact gap that leads toward NP.
A valid schedule must satisfy many constraints at once.
But checking whether a given timetable has clashes is much easier.
Optimization problems quickly become huge as cities grow.
A proposed route can be evaluated much faster than searching all possibilities.
This pushes students to think about the limits of computation itself.
Complexity is about difficulty; some questions also touch computability limits.
Is there a pen? Is this timetable valid? Is this route short enough?
Sometimes search is tiny. Sometimes possibilities explode.
Given a proposed answer, constraints may be checked quickly.
That is where P, NP, NP-Complete, and NP-Hard enter.
Start from scratch and construct an answer.
Fill every blank correctly. Many branches may need to be explored.
Assign all courses to slots while satisfying every clash constraint.
Construct a valid cycle or route, not just check one.
Someone gives a candidate. You only need to test whether it works.
Check rows, columns, and sub-grids for duplicates.
Scan all student pairs or conflict edges for clashes.
Check whether all required cities or vertices appear correctly and whether the cost limit is met.
You may need to search among many possibilities.
Once a candidate is given, checking can be much faster.
Instead of asking “Find the shortest tour”, ask “Is there a tour of length ≤ 100?” That YES / NO version fits more naturally into complexity classes.
Hover or click a region. Then click the example chips below to see where they belong.
This diagram compares efficiently solvable problems, efficiently verifiable problems, and the hardest well-known decision problems.
A reduction transforms one problem into another in polynomial time. If a known hard problem can be converted into a new problem, the new problem must also be hard. "The conversion from A to B takes polynomial time"
“A reduces to B” means: if you can solve B efficiently, then you can also solve A efficiently.
Reduce a known hard problem A → B.
Students often reverse the arrow. The direction matters.
For each variable, create a pair such as x and ¬x. The cover will choose one side from each pair.
Each 3-literal clause becomes a triangle. To cover all its internal edges, the cover chooses 2 vertices from that clause gadget.
If there are l variables and c clauses, then the target size is:
Move the sliders to see how the target cover size changes for a 3-SAT style reduction.