Theory algorithms / interactive lesson
Interactive reduction trainer for complexity theory: choose a reduction, watch how instances are transformed, and learn the board-proof structure for exams.
Language
Reductions default to English. Czech is available here because these lessons already have Czech study notes.
Step 1 / 3
Take an arbitrary instance x of problem A. We are not solving A yet; we only construct an instance f(x) of problem B.
Reduction Companion
Reductions are the main language for comparing computational problems. Instead of solving a problem directly, a reduction shows how every instance of one problem can be translated into an equivalent instance of another problem.
A polynomial many-one reduction U ≤p V constructs, in polynomial time, an instance of V from an instance of U while preserving the YES/NO answer. If V has a polynomial solver, then U also has one. If U is already known to be hard, then V must be at least as hard as U.
A good exam proof has a fixed structure: define both problems, describe the input instance, construct the target instance, prove both directions of the equivalence, argue polynomial size/time, and state the consequence for the complexity class.
Each reduction is stored in its own file. The player only renders generic artifacts such as formulas, graphs, sets, numbers, flow networks, PCP tiles, grammars, or schedules. This makes each reduction easy to rewrite or improve independently.
Code companion
Connect each visual decision to an implementation pattern.
To prove U <=p V:
1. Take an arbitrary instance I of U.
2. Construct an instance J = f(I) of V.
3. Prove: I is YES for U => J is YES for V.
4. Prove: J is YES for V => I is YES for U.
5. Prove that f runs in polynomial time.
6. State the consequence.
For NP-completeness of V:
- show V is in NP;
- choose known NP-complete U;
- prove U <=p V.