12.1 Reducibility
12.1 Reducibility Reducibility is a way to compare problems by asking whether one problem can be solved using another. Suppose we have two decision problems, $A$ and $B$. Each problem asks whether an input belongs to a certain set: $$ x \in A $$ or $$ x \in B $$ We say that $A$ reduces to $B$ if a method for solving $B$ would also give us a method for...