# How to prove a reduction

I'm just a little confused about the wordings for reductions and would appreciate some help as I am very new to reductions.

I have a question where I have two sets, A and B, and I have to provide a reduction A $\leq_p$ B and then I have to prove that the reduction is correct.

What does this mean exactly?

For the reduction portion do I have to:

1. Provide some sort of explanation of B in terms of A?

2. Provide some sort of explanation of A in terms of B?

3. Both 1 & 2?

And then I'm assuming to prove the reduction is correct, I need to show A $\implies$ B as well as B $\implies$ A?

(The exact question has A as the set of un-directed graphs with a Hamiltonian path and B is the set of un-directed graphs with a Hamiltonian cycle)

Any clarification would be greatly appreciated!!

Thanks.

## 1 Answer

Follow the definition of $\leq_p$.

You have to find a function $f$ (define it!), computable in polynomial time (prove this!) such that

$$\begin{array}{l} \forall x.\ x\in A \implies f(x)\in B \\ \forall x.\ x\notin A \implies f(x)\notin B \end{array}$$ (two more proofs!)

More intuitively, $f$ converts instances of $A$ (i.e. $x$) into instances for $B$ ($f(x)$), and must map $A$ inside $B$, and the complement of $A$ inside the complement of $B$. Very, very roughly, it describes how to solve $A$ exploiting $B$.

Finally, never write nonsense formulas like $A \implies B$ since sets do not imply other sets. Try to be as formal as you can, at least when you have not yet mastered the definition.