Reduction
🧩 What is Reduction ? Reduction is a method of showing that one problem is at least as hard as another problem. Formally: A problem A is reducible to a problem B (written A ≤ B A \leq B ) if we can use a solution to B to solve A . In other words: “If we could solve B , then we could also solve A .” ⚙️ Intuitive Idea Think of reduction like this: You already have a machine (or algorithm) that solves problem B . You want to solve problem A . So, you design a translator that converts every instance of A into an instance of B , such that solving the new instance of B automatically gives you the answer to A . This means: If B is easy (decidable), then A is also easy. If A is hard (undecidable), and A ≤ B , then B must also be hard. 🧮 Example 1: Basic Analogy Suppose: Problem A: “Is a number even?” Problem B: “Is a number divisible by 2?” We can reduce A to B by saying: To check if a number is even (A), check if it’s divi...