1
$\begingroup$

I know this is sort of a basic question, but I don't completely understand the following. Let $A$ and $B$ be two problems. If I take one instance $a$ of $A$ and one instance $b$ of $B$, and show the following. Solving $a$ implies solving $b$, and solving $b$ implies solving $a$. Am I showing that $A$ reduces to $B$, $B$ reduces to $A$ or both? How are $A$ and $B$ related using the $\leq_P$ and $=_P$ notation?

$\endgroup$
1
$\begingroup$

Neither -- you can't show a reduction by starting out with an instance of $A$ and an instance of $B$. Instead, a reduction has to be a way of transforming instances of $A$ into instances of $B$, and vice versa.

A reduction from $A$ to $B$ means you give a way of transforming any instance $a$ of $A$ to an instance $f(a)$ of $B$, such that $a$ is a yes-instance of $A$ if and only if $f(a)$ is a yes-instance of $B$. Here $f$ is the reduction, or transformation. Notice that $f(a) = b$ might not just be any instance of $B$, but it might be a very particular instance constructed by our transformation.

For example: suppose $A$ is the problem of determining if a number is even, and $B$ is the problem of determining if a number is a multiple of 10. Then to give a reduction from $A$ to $B$ we could start with a number $n$, and multiply it by $5$. Our reduction is:

f(n) = n * 5

This is a valid reduction because n is an even if and only if n * 5 is a multiple of 10. But, it doesn't construct every possible instance of $B$; only multiples of $5$ are actually constructed as instances of $B$, not all integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.